1.三数之和（15 - 中）
题目描述：给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
示例 :
输入：nums = [-1,0,1,2,-1,-4] 输出：[[-1,-1,2],[-1,0,1]]
思路：先排序方便使用双指针查找元素，核心思想是：遍历数组，先用0 - 当前值作为sum，再使用双指针查找剩余两个元素。
注意：
- 对于含有重复元素的情况直接略过，否则会超时。
- 双指针的左边界为
i + 1。
代码实现：
public List<List<Integer>> threeSum(int[] nums) { Arrays.sort(nums); List<List<Integer>> ans = new ArrayList<>(); for (int i = 0; i < nums.length - 2; ++i) { if (i == 0 || (i > 0 && nums[i] != nums[i - 1])) { int l = i + 1, r = nums.length - 1; while (l < r) { int sum = nums[i] + nums[l] + nums[r]; if (sum == 0) { // 存储结果，数组转集合 ans.add(Arrays.asList(nums[i], nums[l], nums[r])); // 防止相同的元素加入集合 while (l < r && nums[l] == nums[l + 1]) l++; while (l < r && nums[r] == nums[r - 1]) r--; l++; r--; } else if (sum > 0) { r--; } else { l++; } } } } return ans; }
2.最接近的三数之和（16 - 中）
题目描述：给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。
示例 :
输入：nums = [-1,2,1,-4], target = 1 输出：2 解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。
思路：与上题三数之和基本类似的解法，遍历数组，更新三数之和与目标值最小的差值。
注意：当三数之和等于目标值可以直接返回（最近）。
代码实现：
public int threeSumClosest(int[] nums, int target) { Arrays.sort(nums); int closestNum = nums[0] + nums[1] + nums[2]; for (int i = 0; i < nums.length - 2; ++i) { int l = i + 1, r = nums.length - 1; while (l < r){ int threeSum = nums[l] + nums[r] + nums[i]; if (Math.abs(threeSum - target) < Math.abs(closestNum - target)) { closestNum = threeSum; } if (threeSum > target) { r--; } else if (threeSum < target) { l++; } else { return target; } } } return closestNum; }
3.较小的三数之和（259 - 中）
题目描述：给定一个长度为 n 的整数数组和一个目标值 target，寻找能够使条件 nums[i] + nums[j] + nums[k] < target 成立的三元组 i, j, k 个数（0 <= i < j < k < n）。
示例 :
输入: nums = [-2,0,1,3], target = 2 输出: 2 解释: 因为一共有两个三元组满足累加和小于 2: [-2,0,1] [-2,0,3]
思路：殊途同归，本题寻找小于目标值的三元组的个数。注意：若此时右边界组成的三元组符合条件，那么之前的位置都符合条件。
代码实现：
public int threeSumSmaller(int[] nums, int target) { Arrays.sort(nums); int ans = 0; for (int i = 0; i < nums.length - 2; ++i) { int l = i + 1, r = nums.length - 1; while (l < r){ int sum = nums[l] + nums[r] + nums[i]; if (sum >= target) { r--; } else { ans += r - l; l++; } } } return ans; }
4.四数之和（18 - 中）
题目描述：给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。
注意：答案中不可以包含重复的四元组。
示例 :
输入：nums = [1,0,-1,0,-2,2], target = 0 输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
思路：本质不变，在三数之和基础上又加了一层循环。还是注意对于重复值的剔除（跳过）。
代码实现：
public List<List<Integer>> fourSum(int[] nums, int target) { Arrays.sort(nums); List<List<Integer>> ans = new ArrayList<>(); int n = nums.length; for (int i = 0; i < n - 3; i++) { if (i > 0 && nums[i] == nums[i - 1]) continue; for (int j = i + 1; j < n - 2; j++) { if (j > i + 1 && nums[j] == nums[j - 1]) continue; int l = j + 1, r = n - 1; while (l < r) { int sum = nums[i] + nums[j] + nums[l] + nums[r]; if (sum == target) { ans.add(Arrays.asList(nums[i], nums[j], nums[l], nums[r])); while (l < r && nums[l] == nums[l + 1]) l++; while (l < r && nums[r] == nums[r - 1]) r--; l++; r--; } else if (sum > target) { r--; } else { l++; } } } } return ans; }
