Leetcode Problem : 454. 4Sum II

You can find the problem here — 4 Sum II.

Algorithm

1. Store all sums possible by using vectors — nums1 and nums2 in a hashmap
2. Now we will search negative of all sums possible with vectors nums3 and nums4 in the hashmap.
3. In this way our problem of finding sum 0 using 4 arrays is reduced to find sum 0 using 2 arrays.
4. Space required O(n²) for hashmap.
5. Time required O(n²) for forming sums using two vectors.

C++ Solution

#define ll int
class Solution {
public:
    int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
        map<ll,ll> m;
        for(auto i:nums1)
            for(auto j:nums2)
                m[i+j]++;
        ll ans = 0;
        for(auto i:nums3)
            for(auto j:nums4)
                ans+=m[-(i+j)];
        return ans;
    }
};