LEETCODE 454. 4Sum II 解题思路分析

题目大意：

四数相加 II

给定四个包含整数的数组列表 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 。所有整数的范围在 -228 到 228 – 1 之间，最终结果不会超过 231 – 1 。

例如:

输入:
A = [ 1, 2]
B = [-2,-1]
C = [-1, 2]
D = [ 0, 2]
输出:
2
解释:
两个元组如下:
(0, 0, 0, 1) -> A[0] + B[0] + C[0] + D[1] = 1 + (-2) + (-1) + 2=0
(1, 1, 0, 0) -> A[1] + B[1] + C[0] + D[0] = 2 + (-1) + (-1) + 0=0 

---

如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=454

解题思路分析：

本题是 LEETCODE 18. 4Sum 解题思路分析 的续集，该系列题目到目前为止总共出现过4题（还没刷到的除外，比如Two Sum II等），分别为：

• Two Sum
• LEETCODE 15. 3Sum 解题思路分析
• LEETCODE 18. 4Sum 解题思路分析
• 本题 4Sum II

个人认为本题与Two Sum属于同类型题目，主要考察HashMap，而3Sum与4Sum又是另外一个类型，均可使用双指针思路来解题。

分析本题之前，我觉得有必要说下本题与前一集4Sum的区别，虽然都是求4个数和为某个Target的题目，但是区别在于，本题是在4个数组中分别找4个数字，前一题则是在一个数组中找。我们要明白他们在本质上的不同，才能理解为什么不能使用同一种解题方法。当在一个数组中找4个数字时，我们解法使用的时间复杂度为O(n^3)，前两层循环是在找前两个数，第三层循环使用双指针来找后两个数。其实本题也能使用该方法，但是难点在于无法剪枝！4Sum虽然使用了O(n^3)的时间复杂度，但是剪枝操作让其执行次数远远小于n的三次方，剪枝的核心在于，因为只有一个数组，当它排序之后，如果当前数已经大于Target，那么在它后面的其他数字肯定也都大于Target，此时可以结束循环。而回到本题，我们需要在4个数组中分别挑一个数出来，这样，即使当前数字大于Target，我们也不能确定其他数组中挑出的数字是否也都大于Target，这样一来，就没有办法进行剪枝操作了。

那么本题该如何解呢？上文已经说过，本题其实与Two Sum很相似，我们将4个数组分成2组，A，B和C，D，先使用两层循环遍历A和B中所有元素两两之和，并将结果保存至HashMap，其中key为两元素之和，value为该和出现的次数。之后再使用两层循环遍历C和D中所有元素两两之和，并查看该和的相反数在map中存在的个数，并将个数累加至返回结果即可。

实现代码：

public int fourSumCount(int[] A, int[] B, int[] C, int[] D) {
    int length=A.length; // 每个数组长度，4个数组长度一致
    // 记录A和B中每种元素和出现的次数
    Map<Integer, Integer> map=new HashMap<>();
    // 循环数组A
    for(int i=0;i<length;i++){
        // 循环数组B
        for(int j=0;j<length;j++){
            // 取得当前两元素之和已经出现过的次数
            int count = map.getOrDefault(A[i] + B[j],0);
            // 次数加一存入map 
            map.put(A[i] + B[j], count+1);
        }
    }
    int res=0; // 返回结果
    // 循环数组C
    for(int i=0;i<length;i++){
        // 循环数组D
        for(int j=0;j<length;j++){
            // 查看两数和的相反数在map中的个数，并将该个数累加至返回结果
            res+= map.getOrDefault(-C[i] - D[j],0);
        }
    }
    return res;
}

本题解法执行时间为71ms。

Runtime: 71 ms, faster than 86.16% of Java online submissions for 4Sum II.

Memory Usage: 65.5 MB, less than 12.00% of Java online submissions for 4Sum II.

本网站文章均为原创内容，并可随意转载，但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: https://leetcode.jp/leetcode-454-4sum-ii-解题思路分析/