Fork me on GitHub

4SUM II

Posted on

Description

https://leetcode.com/problems/4sum-ii/description/

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27


class Solution {
public:
    int fourSumCount(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D) {
        unordered_map<int, int> X, Y;
        for (int indexA = 0; indexA < A.size(); indexA++) {
            for (int indexB = 0; indexB < B.size(); indexB++) {
                X[A[indexA] + B[indexB]] += 1;
            }
        }
        for (int indexC = 0; indexC < C.size(); indexC++) {
            for (int indexD = 0; indexD < D.size(); indexD++) {
                Y[C[indexC] + D[indexD]] += 1;
            }
        }
        
        int ret = 0;
        for (auto iter = X.begin(); iter != X.end(); iter++) {
            auto iterD = Y.find(-iter->first);
            if (iterD != Y.end()) 
                ret += iter->second * iterD->second;
        }
        
        return ret;
    }
};