454. 四数相加 II

题目链接
代码随想录

分析

首先我们能想到的就是暴力解法四个 for 循环嵌套，好家伙，复杂度是 $O(n\ast n\ast n\ast n)$ ，那我们有没有办法简化呢？说真的还真的很难想到，
我一开始的时候只能想到，我们可以简化最后一层 for 循环，即三层 for 循环 + HashMap 的方式。但是实际上还有更好的简化方式。那就是四个数组降解为两个数组，然后用 HashMap。
怎么降解呢？
我们在 1. 两数之和 这个问题中，是求同一个数组中的两个元素之和，我们把经过的元素全放到 HashMap 中，然后遍历到一个元素，就直接在 HashMap 中查找 target-当前元素，这就将一个 for 循环变成了一个 HashMap 的查找操作，复杂度为 $O(1)$，
拓展一点，如果是两个数组呢？那就更简单了，直接将一个数组的所有元素都放到 HashMap 中，遍历另一个数组的时候，在 HashMap 中查找 target-当前元素，即可。
再拓展一点，如果是四个数组呢？
简单，我们将四个数组分为两组，一个组有两个数组，其中一个组，我们用两层 for 循环，把两个数组的任意组合的和作为 Key,元素的索引作为 List<String> 作为 value 放到 HashMap 里面，当然如果不需要记录索引，可以不记录这个 value。对于另一个组，我们可以同样用两层 for 循环，把两个数组的任意组合的和求出来，然后在上一组的 HashMap 中查找 target-当前和，这样就将 $O(n\ast n)$ 变成了 $O(2\ast n\ast n)$ ，即 $O(2\ast n\ast n)$ 。
在当前这个题中，第一组获取 HashMap 的时候， HashMap 保存两个数组元素和出现的次数即可，在遍历第二组元素的时候，将所有在 HashMap 中查找 target-当前和 的结果累加起来，就是组合的个数。

这种通过将两个 for 循环嵌套起来，实现四个数组变成 2 个数组的做法，还真的挺难想的，主要是我们做算法题的时候，天生就抗拒 for 循环嵌套，都没忘这方面想。

再拓展一点，如果是三个数组呢？
那就是两个数组进行 for 循环嵌套获取 HashMap，遍历最后一个数组，在 HashMap 中查找 target-当前元素。

后面做了 15. 三数之和、18. 四数之和 之后再回来看这个题，才发现这个题跟 1. 两数之和，15. 三数之和、18. 四数之和 本质上的区别就是，前面这些题目都是在一个数组里面和为某个值的元素组合，而且元素不能重复使用，而这道题目是四个独立的数组，只要找到 A[i] + B[j] + C[k] + D[l] = 0 就可以，不用考虑有重复的四个元素相加等于 0 的情况，所以相对于前面三题，还是简单了不少！

解题

public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
    HashMap<Integer,Integer> twoArraySumMap = new HashMap<Integer,Integer>();
    for(int i=0;i<nums1.length;i++){
        for(int j=0;j<nums2.length;j++){
            int sum = nums1[i]+nums2[j];
            int occur = twoArraySumMap.getOrDefault(sum,0);
            twoArraySumMap.put(sum,occur+1);
        }
    }
    int combination = 0;
    for(int i=0;i<nums3.length;i++){
        for(int j=0;j<nums4.length;j++){
            int sum = nums3[i]+nums4[j];
            int occur = twoArraySumMap.getOrDefault(0-sum,0);
            combination+=occur;
        }
    }
    return combination;
}

相关题

1. 两数之和