18.四数之和

crazyjums

LeetCode刷题middle双指针

发布于：Nov 12, 2020

次浏览

18. 四数之和

https://leetcode-cn.com/problems/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]
]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/4sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

1 解题思

思路：排序+双指针

在15. 三数之和的基础上，多定义一个下届即可，定义四个指针，$a,b,c,d$，先固定$a$和$b$，$b=a+1$，然后再定义双指针$c$和$d$，令$c=b+1$，$d=size-1$，然后判断这四个指针的数值的和是否与$target$的结果：

当$nums[a]+nums[b]+nums[c]+nums[d]==target$，符合要求，添加到结果集中
当$nums[a]+nums[b]+nums[c]+nums[d]>target$，太大，应该让指针$d$左移动
当$nums[a]+nums[b]+nums[c]+nums[d]<target$，太小，应该让指针$c$右移动

注意：在计算时，要防止各个指针所指向的值是否想等，如果某一个指针的前一个值和后一个相等，则不参与计算，因为结果集中不能出现重复结果。

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> ans = new ArrayList<>(); 
        int size = nums.length;
        if (size < 4) return ans;
        Arrays.sort(nums);
        for (int a = 0; a <= size- 4; a ++) {
            if (a > 0 && nums[a] == nums[a - 1]) continue; //去重
            for (int b = a + 1; b <= size - 3; b ++) {
                if (b > a + 1 && nums[b] == nums[b - 1]) continue; //去重
                int c = b + 1;
                int d = size - 1;
                while (c < d) {
                    if (nums[a] + nums[b] + nums[c] + nums[d] < target) {
                        c ++;
                    } else if (nums[a] + nums[b] + nums[c] + nums[d] > target) {
                        d --;
                    } else {
                        List<Integer> tem = new ArrayList<>();
                        tem.add(nums[a]);
                        tem.add(nums[b]);
                        tem.add(nums[c]);
                        tem.add(nums[d]);
                        ans.add(tem);
                        while (c < d && nums[c + 1] == nums[c]) c++; //去重
                        while (c < d && nums[d - 1] == nums[d]) d--; //去重
                        c++;
                        d--;
                    }
                }
            }
        }
        return ans;
    }
}