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++，后面的元素可能會有滿足題意的。

如果這篇文章對你有所幫助，請點贊、評論、收藏，創作不易，你的支持是我創作的動力。