4Sum II

Problem

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

HashMap Solution using Two 2Sums

public class Solution {
    public int fourSumCount(int[] a, int[] b, int[] c, int[] d) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i : a) {
            for (int j : b) {
                map.put(i + j, map.getOrDefault(i + j, 0) + 1);
            }
        }
        int count = 0;
        for (int i : c) {
            for (int j : d) {
                count += map.getOrDefault(-(i + j), 0);
            }
        }
        return count;
    }
}

Analysis

As long as you see many sums problem
Divide it into two pars which have some relations
Then using that relations to get the result
We use HashMap in this solution to store every possible 2sum from a and b
Then we loop through every possible 2sum from c and d and see if there are negative sums of that 2sum in the map
If so, we know we can construct a tuple which satisfies problem's requirement
We don't have to remove it, because each possible 2sum itself is unique
Hence there won't be any duplicates