454. 4Sum II

Problem statement:

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.

Example:

Input:
A = [ 1, 2]
B = [-2,-1]
C = [-1, 2]
D = [ 0, 2]

Output:
2

Explanation:
The two tuples are:
1. (0, 0, 0, 1) -> A[0] + B[0] + C[0] + D[1] = 1 + (-2) + (-1) + 2 = 0
2. (1, 1, 0, 0) -> A[1] + B[1] + C[0] + D[0] = 2 + (-1) + (-1) + 0 = 0

Solution:

Compared with 4sum, it is easier as four lists are independent. The most simple solution is four level loops to find the solution by brute force. Time complexity is O(n * n * n * n) as mentioned that the four lists are equal length. Obviously, it is not good.

We choose hash tables to optimize the solution.

The basic idea:

• Two hash tables, one for A and B, another for C and D. They store the sum and the number of the sum.
• Find all sum in A and B. O(n * n)
• Find all sum in C and D. O(n * n)
• Two level loops in these two hash table to find the number. If the sum is 0, we should do multiplication for these two numbers. O(n * n)

Time complexity is O(n * n), it greatly improved the efficiency.

class Solution {
public:
    int fourSumCount(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D) {
        unordered_map<int, int> ab;
        unordered_map<int, int> cd;
        for(vector<int>::size_type ix = 0; ix < A.size(); ix++){
            for(vector<int>::size_type iy = 0; iy < B.size(); iy++){
                ab[A[ix] + B[iy]]++;
            }
        }
        for(vector<int>::size_type ix = 0; ix < C.size(); ix++){
            for(vector<int>::size_type iy = 0; iy < D.size(); iy++){
                cd[C[ix] + D[iy]]++;
            }
        }
        int sum_cnt = 0;
        for(auto it : ab){
            if(cd.find(-it.first) != cd.end()){
                sum_cnt += it.second * cd[-it.first];
            }
        }
        return sum_cnt;
    }
};