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属于同类型题目,主要考察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-解题思路分析/
此条目发表在leetcode分类目录,贴了, , 标签。将固定链接加入收藏夹。

LEETCODE 454. 4Sum II 解题思路分析》有1条回应

  1. Pingback引用通告: LEETCODE 16. 3Sum Closest 解题思路分析 - LEETCODE从零刷LEETCODE从零刷

发表评论

电子邮件地址不会被公开。