C++_O(n^2)


  • 0
    class Solution {
    public:
    int fourSumCount(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D) {
        int n = A.size();
        int res = 0;
        unordered_map<int,int> mp1;
        unordered_map<int,int> mp2;
        for(int i = 0; i < n; ++i){
            for(int j = 0; j < n; ++j){
                int sum1 = A[i] + B[j];
                int sum2 = C[i] + D[j];
                if(mp1.find(sum1) == mp1.end()) mp1[sum1] = 0;
                if(mp2.find(sum2) == mp2.end()) mp2[sum2] = 0;
                mp1[sum1]++;
                mp2[sum2]++;
            }
        }
        for(auto num1 : mp1){
            int number = num1.first;
            if(mp2.find(-1 * number) != mp2.end()){
                res += num1.second * mp2[-1*number];
            }
        }
        return res;
    }
    };

Log in to reply
 

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