454. 4Sum II

在四个不同的数组中寻找和为0的一组数字。根据数据规模: N<=500 计算

>>> 500 ** 4
62500000000
>>> 500 ** 3
125000000
>>> 500 ** 2
250000

可知O(n^2)的算法可行，所以将四重循环拆成二重。

public int fourSumCount(int[] A, int[] B, int[] C, int[] D) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int a : A) {
        for (int b : B) {
            map.put(a + b, map.getOrDefault(a + b, 0) + 1);
        }
    }

    int res = 0;
    for (int c : C) {
        for (int d : D) {
            if (map.containsKey(- c - d)) 
                res += map.get(-c -d);
        }
    }
    return res;
}