Finding Pairs With a Certain Sum
给两个数组设计一个数据结构, 可以add一个数字到第二个数组, 还有count两个数组的数字等于total有几对儿.
这个就是第一个数组大, 第二个小, 所以先处理大的数组. 然后count的时候直接减一下即可.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
class FindSumPairs { public: unordered_map<int, int> map; vector<int> n1; vector<int> n2; FindSumPairs(vector<int>& nums1, vector<int>& nums2) { n1 = nums1; n2 = nums2; for(auto n : n2) map[n]++; } void add(int index, int val) { map[n2[index]]--; map[n2[index] + val]++; n2[index] += val; } int count(int tot) { int res = 0; for(int n : n1) res += map[tot - n]; return res; } }; /** * Your FindSumPairs object will be instantiated and called as such: * FindSumPairs* obj = new FindSumPairs(nums1, nums2); * obj->add(index,val); * int param_2 = obj->count(tot); */ |