1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        Map<Integer, Integer> sumPairCount = new HashMap<>();
        for (int i = 0; i < nums1.length; i++) {
            for (int j = 0; j < nums2.length; j++) {
                sumPairCount.put(nums1[i] + nums2[j], sumPairCount.getOrDefault(nums1[i] + nums2[j], 0) + 1);
            }
        }
        int ans = 0;
        for (int i = 0; i < nums3.length; i++) {
            for (int j = 0; j < nums4.length; j++) {
                ans += sumPairCount.getOrDefault(-(nums3[i] + nums4[j]), 0);
            }
        }
        return ans;
    }
}

分治的思想, 我们看前两个nums array组成的所有pair的值有哪些, 然后我们统计每一个值能组成的pair的个数到map里面. 我们再遍历后两个array的每种组合, 看看它们缺的那一半在map中有没有, 如果有看有几对, 这样就是当前pair和之前nums1和nums2组成的pair的组合数, 加到ans上即可.

时间复杂度: O(n^2)
空间复杂度: O(n^2)