LEETCODE 18. 4Sum 解题思路分析

题目大意：

四数之和

给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。

注意：

答案中不可以包含重复的四元组。

示例：

给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。

满足要求的四元组集合为：
[
   [-1,  0, 0, 1],
   [-2, -1, 1, 2],
   [-2,  0, 0, 2]
] 

---

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

解题思路分析：

本题是 LEETCODE 15. 3Sum 解题思路分析 的续集，这两题的思路没有太大区别，如果没有做3sum，建议先了解一下上一题的解法，然后再用本题来练手。

4个数之和，实际上可以理解为1个数加上3个数，3个数之和即是3sum的思路，在该思路基础上，再多加一层循环即可。时间复杂度为O(n^3)

实现代码：

public List<List<Integer>> fourSum(int[] nums, int target) {
    Arrays.sort(nums); // 排序数组
    // 返回结果
    List<List<Integer>> res = new ArrayList<>();
    // 循环数组
    for(int i=0;i<nums.length;i++){
        // 取得第一个数字
        int n1=nums[i];
        // 如果当前数字大于0并且大于target，说明它加上另外3数一定大于target，退出
        if(n1>0&&n1>target) break;
        // 当前数字等于前一位的数字，为了防止重复，跳过
        if(i>0&&n1==nums[i-1]) continue;
        // 循环找第二个数字，以下为3sum的解法
        for(int j=i+1;j<nums.length;j++){
            int n2=nums[j];
            if(n2>0&&n1+n2>target) break;
            if(j>i+1&&n2==nums[j-1]) continue;
            int left = j+1,right=nums.length-1;
            while(left<right){
                int n3=nums[left];
                int n4=nums[right];
                int sum=n1+n2+n3+n4;
                if(sum==target){
                    res.add(Arrays.asList(n1,n2,n3,n4));
                    while(left<right&&nums[left]==n3) left++;
                    while(left<right&&nums[right]==n4) right--;
                }else if(sum<target){
                    left++;
                }else{
                    right--;
                }
            }
        }
    }
    return res;
}

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

Runtime: 22 ms, faster than 66.07% of Java online submissions for 4Sum.

Memory Usage: 44.1 MB, less than 34.78% of Java online submissions for 4Sum.

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