主題
題目連結：
題目意譯：
你被給定兩個整數陣列 nums1 和 nums2 。你被要求實作一個資料結構其支援以下兩種詢問：
將陣列 nums2 中的給定索引值位置之元素加上一正整數。
計算 (i, j) 數對之數量，其滿足 nums1[i] + nums2[j] 等於一個給定的值（0 ≦ i < nums1.length 且 0 ≦ j < nums2.length）。
實作類別 FindSumPairs：
FindSumPairs(int[] nums1, int[] nums2) 初始化一個 FindSumPairs 物件有著兩個整數陣列 nums1 和 nums2 。
void add(int index, int val) 將 nums2[index] 加上 val ，即執行 nums2[index] += val 。
int count(int tot) 回傳 (i, j) 數對之數量，其滿足 nums1[i] + nums2[j] 等於 tot 。
限制：
1 ≦ nums1.length ≦ 1000
1 ≦ nums2.length ≦ 10 ^ 5
1 ≦ nums1[i] ≦ 10 ^ 9
1 ≦ nums2[i] ≦ 10 ^ 5
0 ≦ index < nums2.length
1 ≦ val ≦ 10 ^ 5
1 ≦ tot ≦ 10 ^ 9
最多呼叫 add 和 count 各 1000 次。
範例測資：
輸入
["FindSumPairs", "count", "add", "count", "count", "add", "add", "count"]
[[[1, 1, 2, 2, 2, 3], [1, 4, 5, 2, 5, 4]], [7], [3, 2], [8], [4], [0, 1], [1, 1], [7]]
輸出
[null, 8, null, 2, 1, null, null, 11]
解釋
FindSumPairs findSumPairs = new FindSumPairs([1, 1, 2, 2, 2, 3], [1, 4, 5, 2, 5, 4]);
findSumPairs.count(7); // 回傳 8 ；數對 (2,2) 、 (3,2) 、 (4,2)、 (2,4) 、 (3,4) 、 (4,4) 得出 2 + 5 而數對 (5,1) 、 (5,5) 得出 3 + 4
findSumPairs.add(3, 2); // 現在 nums2 = [1,4,5,4,5,4]
findSumPairs.count(8); // 回傳 2 ；數對 (5,2) 、 (5,4) 得到 3 + 5
findSumPairs.count(4); // 回傳 1 ；數對 (5,0) 得 3 + 1
findSumPairs.add(0, 1); // 現在 nums2 = [2,4,5,4,5,4]
findSumPairs.add(1, 1); // 現在 nums2 = [2,5,5,4,5,4]
findSumPairs.count(7); // 回傳 11 ；數對 (2,1) 、 (2,2) 、 (2,4) 、 (3,1) 、 (3,2) 、 (3,4) 、 (4,1) 、 (4,2) 、 (4,4) 得 2 + 5 而數對 (5,3) 、 (5,5) 得 3 + 4
解題思維：
可以看到在大部分情況下， nums1 的長度都小於 nums2 的長度。因此窮舉 nums1 中的元素比窮舉 nums2 中的元素還要來得快。
因此我們可以將 nums2 再多用一個雜湊表 H 儲存，其鍵值為一整數，而映射值為 nums2 中有多少元素值為該整數。
因此當呼叫 add(index, val) 時，我們除了更動 nums2[index] 以外，還會先將 H[nums2[index]] 減去 1 （因為 nums2 中等於 nums2[index] 這個值的元素少一個了）。然後再一同使 nums2[index] += val 並將 H[nums2[index]] 加 1 。
而當呼叫 count(tot) ，我們就窮舉 nums1 中的所有元素。對於每個元素 nums1[i] ，我們去找 H 中是否存在 H[tot - nums1[i]] 。將所有的 H[tot - nums1[i]] 加總即是回傳值。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
