1865: Finding-Pairs-With-a-Certain-Sum
Medium

table of contents

The first solution I thought of occured when I saw the restraints for nums1 and nums2.

After seeing that 1 <= nums1.length <= 1000 and 1 <= nums2.length <= 10^5, there must exist a solution which revolved around placing all nums2 elements into a hashmap, then iterating through nums1 (since it is wayyyyy smaller) to see how many of the corresponding number in nums2 exists.

Therefore,

code

class FindSumPairs {
public:
    vector<int> arr1;
    vector<int> arr2;
    unordered_map<int, int> mp;
    FindSumPairs(vector<int>& nums1, vector<int>& nums2) {
        arr1 = nums1;
        arr2 = nums2;
        for (int& num : arr2) {
            ++mp[num];
        }
    }
    
    void add(int index, int val) {
        --mp[arr2[index]];
        arr2[index] += val;
        ++mp[arr2[index]];
    }
    
    int count(int tot) {
        int ans = 0;
        for (int& num : arr1) {
            int difference = tot-num;
            if (mp.count(difference)) {
                ans += mp[difference];
            }
        }
        return ans;
    }
};

/**
 * Your FindSumPairs object will be instantiated and called as such:
 * FindSumPairs* obj = new FindSumPairs(arr1, arr2);
 * obj->add(index,val);
 * int param_2 = obj->count(tot);
 */

complexity

learnings

if (mp.count(difference)) {
    ans += mp[difference];
}

time taken