Concise hash map O(n^2) solution with explanation, c++


  • 6
    I

    Using 2 hash maps for each of possible sums in both (A,B) and (C,D) find number of occurrences of this sum. Then, for each sum in (A,B) we can find if (C,D) contains complimentary sum. Add (this sum occurrences(a,b)) * (complimentary sum occurrences(c,d)) to the result.

    class Solution {
    public:
        void fillMap(vector<int>& A, vector<int>& B, unordered_map<int,int> &m)
        {
            int n = A.size();
            for(int i = 0; i < n; ++i)
            for(int j = 0; j < n; ++j)
              ++m[A[i] + B[j]];
              
        }
        int fourSumCount(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D) {
            unordered_map<int,int> m1, m2;
            fillMap(A, B, m1);
            fillMap(C, D, m2);
            int res = 0;
            for(auto it = m1.begin(); it != m1.end(); ++it)
            {
               auto it2 = m2.find(-it->first);
               if(it2 != m2.end())
                 res += it->second*it2->second;
            }
            return res;
        }
    };
    

  • 1
    M

    How this line gives the result,
    Add (this sum occurrences(a,b)) * (complimentary sum occurrences(c,d)) to the result.
    please provide a mathematical explanation.


  • 1
    I

    A[i] + B[j] + C[k] + D[l] == 0. Hence A[i] + B[j] == -(C[k] + D[l]). Let A[i] + B[j] == sum. Then C[k] + D[l] == -sum. We can get sum combining different elements of A and B. Same with -sum and C and D. Total number of 4-tuples (i,j,k,l) for this sum is pairs_number(sum,A,B) times pairs_number(-sum,C,D). For any(i,j) pair in (sum,A,B) we can combine this pair with any pair (k,l) in (-sum,C,D) to get A[i] + B[j] + C[k] + D[l] == 0


  • 0
    L

    Nice solution. A bit more concise:

            for (auto n1:m1){
               res +=m2[-n1.first]*n1.second;
            }
    

  • 0
    G

    @i9r0k I use one hash map. The runtime seems slightly improved.

    int fourSumCount(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D) {
        unordered_map<int, int> ump1;
        int ans = 0;
        for (auto & a:A) {
            for (auto & b:B) {
                if (ump1.find(a+b)==ump1.end()) ump1[a+b]=1; 
                else ump1[a+b] += 1; } }
    
        for (auto & c:C) {
            for (auto & d:D) {
                auto x = ump1.find(-c-d); 
                if (x!=ump1.end()) ans += ump1[-c-d]; } }
        
        return ans; }

  • 0
    S

    Thanks, easy to understand.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.