454.四数相加Ⅱ

难度：中等

给你四个整数数组 nums1、nums2、nums3 和 nums4 ，数组长度都是 n ，请你计算有多少个元组 (i, j, k, l) 能满足：

0 <= i, j, k, l < n
nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0

示例 1：

输入：nums1 = [1,2], nums2 = [-2,-1], nums3 = [-1,2], nums4 = [0,2]
输出：2
解释：
两个元组如下：
1. (0, 0, 0, 1) -> nums1[0] + nums2[0] + nums3[0] + nums4[1] = 1 + (-2) + (-1) + 2 = 0
2. (1, 1, 0, 0) -> nums1[1] + nums2[1] + nums3[0] + nums4[0] = 2 + (-1) + (-1) + 0 = 0

示例 2：

输入：nums1 = [0], nums2 = [0], nums3 = [0], nums4 = [0]
输出：1

提示：

n == nums1.length
n == nums2.length
n == nums3.length
n == nums4.length
1 <= n <= 200
-2^(28) <= nums1[i], nums2[i], nums3[i], nums4[i] <= 2^(28)

解题思路

暴力的做法是：四重循环，遍历所有的元素，看相加结果是否等于目标值，碰到符合要求的元素返回其索引。

但这种做法的时间复杂度为 O(n^4)，这也太高了。

结合 1.两数之和 的做法，考虑使用哈希表来提高查询速度。

我的思路：

设定 res 来记录组合方案数目
设定一个 HashMap 用来存储遍历 nums1 数组和 nums2 数组的元素和，其中 key 为和，value 为此和的 当前组合方案个数
双层循环遍历 nums1 数组和 nums2 数组，对 map 进行初始化
再进行一个双层循环，遍历 nums3 数组和 nums4 数组，得到 0 - ( nums3[i] + nums4[j] ) 的值，此时可直接查询 map 来获取到该值对应的方案数，并累计在 res 里
返回 res ，其值即为所有的组合方案的个数

我的代码

java

public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
    Map<Integer, Integer> map = new HashMap<>();
    int res = 0;
    // 计算nums1和nums2中所有元素组合的和，并记录每个和出现的次数
    for (int i = 0; i < nums1.length; i++) {
        for (int j = 0; j < nums2.length; j++) {
            int one = nums1[i] + nums2[j];
            map.put(one, map.getOrDefault(one, 0) + 1);
        }
    }
    // 遍历nums3和nums4的所有元素组合
    for (int i = 0; i < nums3.length; i++) {
        for (int j = 0; j < nums4.length; j++) {
            int two = nums3[i] + nums4[j];
            int one = -two;
            // 如果one在之前的组合中出现过，则计入结果
            res += map.getOrDefault(one, 0);
        }
    }
    return res;
}

时间复杂度：O(n^2)

空间复杂度：O(n^2)，最坏情况下 nums1[i] 和 nums1[j] 的值各不相同，相加产生的数字个数为 n^2

总结

什么时候使用哈希法：

当我们需要快速查询一个元素是否出现过，或者一个元素是否在集合里的时候，就要第一时间想到哈希法。

本题，我们不仅要知道元素有没有遍历过，还要知道这个元素对应的下标，需要使用 key value 结构来存放，key 来存元素，value 来存下标，那么使用 map 正合适。

使用数组和 set 来做哈希法的局限：

数组的大小是受限制的，而且如果元素很少，而哈希值太大会造成内存空间的浪费。
set 是一个集合，里面放的元素只能是一个 key，而本题，不仅要判断 y 是否存在而且还要记录 y 的下标位置，因为要返回 x 和 y 的下标。所以 set 也不能用。

454.四数相加Ⅱ ​

解题思路 ​

我的代码 ​

总结 ​

454.四数相加Ⅱ

解题思路

我的代码

总结