【力扣 Hot100】 刷题日记——双指针的经典应用
D11 两数之和 II - 输入有序数组
LCR 006. 两数之和 II - 输入有序数组 - 力扣（LeetCode）
这道题目也是双指针的一个典型应用，题目要求找出和为target的两个数字的下标，并且告诉了有且仅有一对符合条件的数字。
而且题目已经给排好序了，这道题目其实可以暴力匹配嵌套for循环来解决，但是排序就没用了。。如果还记得盛水最多的容器这道题目的话，我们可以用相同的操作，两个指针分别为left和right，两边到中间扫描，如果两数相加大于target，那么显然需要减小右端的数值，也就是right--。反之，增大左端的数值，也就是left++，直到两端的和为target，这个问题就解决了。
class Solution { public int[] twoSum(int[] numbers, int target) { int l = 0; int r = numbers.length - 1; while(l < r){ if(numbers[l] + numbers[r] > target){ r--; }else if(numbers[l] + numbers[r] < target){ l++; }else{ return new int[]{l, r}; } } return new int[]{}; }}三数之和
15. 三数之和 - 力扣（LeetCode）
这道题目跟上道题目很像，其实是延续了上道题目的做法，这道题目要求判断是否存在三元组，使得三者之和为0，并且要求不能重复。
有了上一道题的启发，我们不管三七二十一，先给他排序，有序总比无序容易处理。我们大体想一下，虽然这是求三个数的和，无非就是固定一个数num，其他两个数nums[l] nums[r]，继续二数之和的操作。当找到一个解时，跳过与nums[l] nums[r]相同的值，避免产生重复三元组。
解题思路
- 先排序，把数组变为非降序
- 固定第一个数
num = num[i]，在他右侧用双指针(l,r)寻找符合num + nums[l] + nums[r] = 0的数值 - 去重，找到解时，跳过与
nums[l] nums[r]相同的值，避免产生重复三元组。 - 优化，利用排序后“最小/最大可能和”的上下界，提前 break/continue，减少无效枚举。
这个题目的难点在于去重和剪枝优化，涉及到两次去重两次剪枝。
if(i > 0 && num == nums[i - 1]) continue;● 去重1（对 i）：如果当前 x 和上一个相同，那么以它为首的三元组会和上次完全重复，直接跳过。
if (x + nums[i + 1] + nums[i + 2] > 0) break; // 优化一● 优化一（上界剪枝）：数组有序时，固定 x 后，能得到的最小三数和是 x + nums[i+1] + nums[i+2]（取右侧最小的两个数）。
● 若这个最小和已经大于 0，那么无论 j,k 取什么，都只会更大 ⇒ 后续 i 也不可能成功 ⇒ 可以直接 break 结束外层循环。
if (x + nums[n - 2] + nums[n - 1] < 0) continue; // 优化二● 优化二（下界剪枝）：固定 x 后，能得到的最大三数和是 x + nums[n-2] + nums[n-1]（取右侧最大的两个数）。
● 若这个最大和仍然小于 0，说明以 x 为首无论怎么取都不够大，不可能凑到 0 ⇒ 换更大的首元素，continue。
两个优化都建立在“数组已排序”的前提上，能显著减少双指针的启动次数与无效移动。
class Solution { public List<List<Integer>> threeSum(int[] nums) { Arrays.sort(nums); List<List<Integer>> ans = new ArrayList<>(); int n = nums.length; for (int i = 0; i < n - 2; i++) { //因为是三元组，所有只需要到n-3 int num = nums[i]; if(i > 0 && num == nums[i - 1]) continue; //去掉重复部分 if(num + nums[i + 1] + nums[i + 2] > 0) break; //后边部分的和绝对都大于0，没有必要在循环下去 if(num + nums[n - 1] + nums[n - 2] < 0) continue; //说明当前数字与最大的两个值的和仍小于0，直接跳到下一个数字 int l = i + 1; // 二数之和的左右边界 int r = n - 1; while(l < r){ if(num + nums[l] + nums[r] > 0){ r--; }else if(num + nums[l] + nums[r] < 0){ l++; }else{ ans.add(List.of(num, nums[l], nums[r])); for(l++; l < r && nums[l] == nums[l - 1]; l++);//过滤掉与当前解涉及元素相同的部分 for(r--; r > l && nums[r] == nums[r + 1]; r--); } } } return ans; }}其实代码还可以优化，
if(num + nums[i + 1] + nums[i + 2] > 0) break; if(num + nums[n - 1] + nums[n - 2] < 0) continue; 如果当前连续三个值之和大于0，那就不用往后看了，后面的一定大于0。
如果当前值与最大两值之和小于0，也不用看了，说明num = nums[i]，至少这个值不符合题意，但是i++，后面的元素可能会有满足题意的。
如果这篇文章对你有所帮助，请点赞、评论、收藏，创作不易，你的支持是我创作的动力。
