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-3int 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++，后面的元素可能会有满足题意的。

如果这篇文章对你有所帮助，请点赞、评论、收藏，创作不易，你的支持是我创作的动力。