2020

给定一个包含 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 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

经典抄题解。思路是枚举前两个数，用双指针找后两个数，期间可以加上一些剪枝。 为了去重，再每次移动某一个指针的时候都移动到数字发生变化为止。

class Solution { public List<List<Integer>> fourSum(int[] nums, int target) { Arrays.sort(nums); List<List<Integer>> ret = new ArrayList<>(); //题解的方法 枚举前两个 双指针后两个 int n = nums.length; for(int r1 = 0; r1 < n - 3; ++r1) { int n1 = nums[r1]; if(n1 + nums[r1 + 1] + nums[r1 + 2] + nums[r1 + 3] > target) { break; } if(n1 + nums[n - 3] + nums[n - 2] + nums[n - 1] < target) { continue; } for(int r2 = r1 + 1; r2 < n - 2; ++r2) { int r3 = r2 + 1, r4 = n - 1, n2 = nums[r2]; if(n1 + n2 + nums[r2 + 1] + nums[r2 + 2] > target) { break; } if(n1 + n2 + nums[n - 2] + nums[n - 1] < target) { continue; } while(r3 < r4) { int n3 = nums[r3], n4 = nums[r4]; int sum = n1 + n2 + n3 + n4; if(sum == target) { ret.add(List.of(n1, n2, n3, n4)); while(r3 <= r4 && nums[r3] == n3) { ++r3; } while(r3 <= r4 && nums[r4] == n4) { --r4; } } else if(sum > target) { while(r3 <= r4 && nums[r4] == n4) { --r4; } } else { while(r3 <= r4 && nums[r3] == n3) { ++r3; } } } while(r2 < n - 1 && nums[r2 + 1] == n2) { ++r2; } } while(r1 < n - 1 && nums[r1 + 1] == n1) { ++r1; } } return ret; } }

题解中给出的剪枝方法为，第一重循环时，如果连着往后四个数都大于target，那么之后r1往右移也没戏，跳出循环；如果和末尾的三个数之和小于target，说明r2选什么都不好使，则r1右移进行下一轮循环。 第二轮循环类似。