LeetCode 454. 4Sum II (Hash Table)

Given four lists A, B, C, D of integer values, compute how many tuples (i, j, k, l) there are such that A[i] + B[j] + C[k] + D[l] is zero.

To make problem a bit easier, all A, B, C, D have same length of N where 0 ≤ N ≤ 500. All integers are in the range of -228 to 228 - 1 and the result is guaranteed to be at most 231 - 1.

C++

class Solution {
    public:
       int fourSumCount(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D){
           unordered_map<int, int> umap;
           //遍历A和B,统计两个数组元素之和,和出现的次数,放到map中
           for(int a : A){
                for(int b : B){
                    umap[a + b]++;
                }
           }
           int cnt = 0;
           //遍历C和D
           for(int c : C){
                for(int d : D){
                    if(umap.find(0 - (c + d)) != umap.end()){
                        cnt += umap[0 - (c + d)];
                    }
                }
           }
           return cnt;
       }
};

和3sum 2sum不同，这里4个不同的数组，2层遍历足够