【LeetCode刷题日记】454：四数相加Ⅱ

前言： 经过前面的学习，我们已经知道了哈希表的三种实现方式的选择，后面我们继续学习哈希表的相关算法题，学会融会贯通，增强对哈希表的理解能力。

题目背景：LeetCode454

给定四个包含整数的数组列表 A , B , C , D ,计算有多少个元组 (i, j, k, l) ，使得 A[i] + B[j] + C[k] + D[l] = 0。 为了使问题简单化，所有的 A, B, C, D 具有相同的长度 N，且 0 ≤ N ≤ 500 。所有整数的范围在 -2^28 到 2^28 - 1 之间，最终结果不会超过 2^31 - 1 。 例如: 输入:

• A = [ 1, 2]
• B = [-2,-1]
• C = [-1, 2]
• D = [ 0, 2]

输出: 2 解释: 两个元组如下:

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

题目答案：

class Solution {
    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        int res = 0;
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        //统计两个数组中的元素之和，同时统计出现的次数，放入map
        for (int i : nums1) {
            for (int j : nums2) {
                int sum = i + j;
                map.put(sum, map.getOrDefault(sum, 0) + 1);
            }
        }
        //统计剩余的两个元素的和，在map中找是否存在相加为0的情况，同时记录次数
        for (int i : nums3) {
            for (int j : nums4) {
                res += map.getOrDefault(0 - i - j, 0);
            }
        }
        return res;
    }
}

题目解析：

关于这个题目，最简单的思路就是用for循环进行多层的循环嵌套，但是时间复杂度比较高，因此我们的目的是把暴力四重循环 O(n4) 的时间复杂度优化到 O(n2)，尽可能的把时间复杂度降低，下面看具体的实现思路：

首先要明白我们要干什么

nums1的一个数 + nums2的一个数 + nums3的一个数 + nums4的一个数 = 0

首先我们先把返回值搞清楚，需要返回的是有几组，所以我们直接定义int res=0；之后再进行修改。

然后接下来我们的逻辑就是计算数组之间的和，我们一开始想到的就是for循环进行四重遍历，但时间复杂度太高，因此我们在这里使用两个循环嵌套的方式，降低的时间复杂度，第一个循环的嵌套计算的前两个数组的所有和，过程如下：

nums1 = [A, B]nums2 = [C, D] 执行顺序是：

1. 外层循环先拿 A
   • 内层循环拿 C → A+C
   • 内层循环拿 D → A+D
2. 外层循环再拿 B
   • 内层循环拿 C → B+C
   • 内层循环拿 D → B+D

计算完sum之后，我们需要创建一个Map集合来存放，因为把 “前两个数的和” 当成 key，把 “这个和出现了几次” 当成 value，提前存好，方便后面快速查找，不用再重复计算。创建 map 就是为了：用空间换时间，把重复计算变成一次查找。大大减少了时间复杂度。相当于一个统计表，后面我们要用到前面两个数组的和是直接进行查找。

因此这里：map.put(sum, map.getOrDefault(sum, 0) + 1);的意思是，我们把计算出来的sum，看看它之前出现过几次（没有就是 0）这次又出现一次，所以次数 +1再把新次数存回去。

接下来：res += map.getOrDefault(0 - i - j, 0);

假设：

• nums3 取的数：2
• nums4 取的数：3

那么：

• i + j = 5
• 需要前两个数的和 = 0 - 5 = -5

去 map 里查 -5 出现了 4 次→ res += 4→ 总数直接加 4,没有就返回0. 因此最后直接返回res。

结语：如果对你有帮助，请点赞，关注，收藏，你的支持就是我最大的鼓励！