Algorithm

LeetCode/4Sum II

Problem Summary

Given four integer arrays A,B,C,D, which have the same length of N where 0 ≤ N ≤ 500, compute the number of tuples (i,j,k,l) such that A[i] + B[j] + C[k] + D[l] == 0.

Solution 1

We can use a map to count the numbers of all possible values of A[i] + B[j] , where 1 ≤ i,j ≤ N. Then we enumerate k and l, and add the number of -C[k]-D[l] to the answer.
The time complexity is O(N^2).

Solution 2

We use array AB to store all possible values of A[i]+B[j], and array CD to store all possible values of -C[k]-D[l]. Then we sort AB and CD respectively. Now we only need to find how many pairs of equal values in AB and CD there are. This can be done with O(N^2) time, so the total time complexity is also O(N^2).

Code for Solution 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int fourSumCount(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D) {
        int n = A.size(), ans = 0;
        unordered_map<int,int> sum;
        for (int i = 0; i < n; ++i)
        	for (int j = 0; j < n; ++j)
        		++sum[A[i]+B[j]];
        for (int i = 0; i < n; ++i)
        	for (int j = 0; j < n; ++j)
        		ans += sum[0-C[i]-D[j]];
        	
        return ans;
    }
};

Code for Solution 2

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
class Solution {
public:
    int fourSumCount(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D) {
        int n = A.size(), total, ans = 0;
        total = n*n;
        int ab[total+1] = {0}, cd[total+1] = {0};
        int k = 0;
        for (int i = 0; i < n; ++i)
        {
            for (int j = 0; j < n; ++j)
            {
                ab[k] = A[i] + B[j];
                cd[k] = 0 - C[i] - D[j];
                k++;
            }
        }
        sort(ab,ab + total);
        sort(cd,cd + total);
        int i = 0, j = 0;
        while (i < total && j <total)
        {
            if (ab[i] == cd[j])
            {
                int p = i, q = j, count1 = 0, count2 = 0;
                while (p<total && ab[p] == ab[i])
                {
                    ++p;
                    ++count1;
                }
                while (q<total && cd[q] == cd[j])
                {
                    ++q;
                    ++count2;
                }
                ans += count1*count2;
                i = p;
                j = q;
            }
            else
            if (ab[i] > cd[j])
                ++j;
            else
                ++i;
        }
        return ans;
    }
};