[算法] 優先算法(二): 雙指針算法(下)

🌸個人主頁:https://blog.csdn.net/2301_80050796?spm=1000.2115.3001.5343
🏵?熱門專欄:🍕 Collection與數據結構 (91平均質量分)https://blog.csdn.net/2301_80050796/category_12621348.html?spm=1001.2014.3001.5482
🧀Java EE(94平均質量分) https://blog.csdn.net/2301_80050796/category_12643370.html?spm=1001.2014.3001.5482
🍭MySql數據庫(93平均質量分)https://blog.csdn.net/2301_80050796/category_12629890.html?spm=1001.2014.3001.5482
🍬算法(97平均質量分)https://blog.csdn.net/2301_80050796/category_12676091.html?spm=1001.2014.3001.5482
感謝點贊與關注~~~

1. 有效三角形的個數(難度:🔵2度)

OJ鏈接

題目描述

購物車內的商品價格按照升序記錄于數組 price。請在購物車中找到兩個商品的價格總和剛好是 target。若存在多種情況，返回任一結果即可。
示例 1：
輸入：price = [3, 9, 12, 15], target = 18
輸出：[3,15] 或者 [15,3]
示例 2：
輸入：price = [8, 21, 27, 34, 52, 66], target = 61
輸出：[27,34] 或者 [34,27]

算法原理
先將數組排序。
我們可以固定?個==「最?邊」，然后在?這條邊?的有序數組中找出?個?元組==，使這個?元組之和?于這個最?邊。由于數組是有序的，我們可以利?「對撞指針」來優化。
設最?邊枚舉到i 位置，區間[left, right] 是i 位置左邊的區間（也就是?它?的區間）：
- 如果nums[left] + nums[right] > nums[i] ：
  - 說明[left, right - 1] 區間上的所有元素均可以與nums[right] 構成?nums[i] ?的?元組
  - 滿?條件的有right - left 種
  - 此時right 位置的元素的所有情況相當于全部考慮完畢， right– ，進?下?輪判斷
- 如果nums[left] + nums[right] <= nums[i] ：
  - 說明left 位置的元素是不可能與[left + 1, right] 位置上的元素構成滿?條件的?元組
  - left 位置的元素可以舍去， left++ 進?下輪循環
代碼編寫

class Solution {public int triangleNumber(int[] nums) {Arrays.sort(nums);int ret = 0;for (int n = nums.length-1;n >= 2;n--){//n固定最大邊int left = 0;int right = n-1;while (left < right){if (nums[left] + nums[right] <= nums[n]){//舍去比right小的元素left++;}else{//比left大的元素全部符合條件ret+=right-left;right--;}}}return ret;}
}

2.兩數之和(難度:🟢1度)

OJ鏈接

題目描述

給定一個整數數組 nums 和一個整數目標值 target，請你在該數組中找出和為目標值 target 的那兩個整數，并返回它們的數組下標。
你可以假設每種輸入只會對應一個答案。但是，數組中同一個元素在答案里不能重復出現。
你可以按任意順序返回答案。
示例 1：
輸入：nums = [2,7,11,15], target = 9
輸出：[0,1]
解釋：因為 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
示例 2：
輸入：nums = [3,2,4], target = 6
輸出：[1,2]
示例 3：
輸入：nums = [3,3], target = 6
輸出：[0,1]

算法原理
- 初始化left ， right 分別指向數組的左右兩端（這?不是我們理解的指針，?是數組的下
  標）
- 當left < right 的時候，?直循環
  - 當nums[left] + nums[right] == target 時，說明找到結果，記錄結果，并且返回；
  - 當nums[left] + nums[right] < target 時：
    - 對于nums[left] ??，此時nums[right] 相當于是nums[left] 能碰到的最?值（別忘了，這?是升序數組）。如果此時不符合要求，說明在這個數組??，沒有別的數符合nums[left] 的要求了（最?的數都滿?不了你，你已經沒救了）。因此，我們可以?膽舍去這個數，讓left++ ，去?較下?組數據；
    - 那對于nums[right] ??，由于此時兩數之和是?于?標值的， nums[right] 還可以選擇?nums[left] ?的值繼續努?達到?標值，因此right 指針我們按兵不動；
  - 當nums[left] + nums[right] > target 時，同理我們可以舍去nums[right] （最?的數都滿?不了你，你也沒救了）。讓right– ，繼續?較下?組數據，?left 指針不變（因為他還是可以去匹配?nums[right] 更?的數的）。
代碼編寫

class Solution {public int[] twoSum(int[] price, int target) {int left = 0;int right = price.length-1;while (left < right){if (price[left]+price[right] == target){return new int[]{price[left],price[right]};}else if (price[left]+price[right] < target){left++;}else{right--;}}return new int[0];}
}

3. 三數之和(難度:🟠4度)

OJ鏈接

題目描述

給你一個整數數組 nums ，判斷是否存在三元組 [nums[i], nums[j], nums[k]] 滿足 i != j、i != k 且 j != k ，同時還滿足 nums[i] + nums[j] + nums[k] == 0 。請
你返回所有和為 0 且不重復的三元組。
注意：答案中不可以包含重復的三元組。
示例 1：
輸入：nums = [-1,0,1,2,-1,-4]
輸出：[[-1,-1,2],[-1,0,1]]
解釋：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元組是 [-1,0,1] 和 [-1,-1,2] 。
注意，輸出的順序和三元組的順序并不重要。
示例 2：
輸入：nums = [0,1,1]
輸出：[]
解釋：唯一可能的三元組和不為 0 。
示例 3：
輸入：nums = [0,0,0]
輸出：[[0,0,0]]
解釋：唯一可能的三元組和為 0 。

算法原理
與兩數之和稍微不同的是，題?中要求找到所有「不重復」的三元組。那我們可以利?在兩數之和那??的雙指針思想，來對我們的暴?枚舉做優化：
- 先排序；
- 然后固定?個數a ：
- 在這個數后?的區間內，使?「雙指針算法」快速找到兩個數之和等于-a 即可。
  但是要注意的是，這道題??需要有==「去重」操作==~
- 找到?個結果之后， left 和right 指針要「跳過重復」的元素；
- 當使?完?次雙指針算法之后，固定的a 也要「跳過重復」的元素。

最后一點要注意的是在去重操作移動指針的時候,不要出現越界情況.
還有一點小優化就是,在i遍歷到>0的數據的時候,就可以停止了,這是因為在剩下的數字中再也找不得兩個數字加起來等于負數了.

代碼編寫

class Solution {public List<List<Integer>> threeSum(int[] nums) {List<List<Integer>> ret = new ArrayList<>();Arrays.sort(nums);for (int i = 0;i < nums.length;){if (nums[i] > 0){//遇到大于0的,一定沒有兩個數使得條件成立break;}int left = i + 1;int right = nums.length-1;while(left < right){if (nums[left] + nums[right] == -nums[i]){List<Integer> a = new ArrayList<>();a.add(nums[i]);a.add(nums[left]);a.add(nums[right]);ret.add(a);left++;right--;while(left < nums.length && nums[left] == nums[left-1]){//left去重,且不可以越界left++;}while(right > 0 && nums[right] == nums[right+1]){//right去重且不可以越界right--;}}else if (nums[left] + nums[right] < -nums[i]){//與前面兩數之和的原理相同left++;}else{right--;}}//i去重i++;while(i < nums.length && nums[i] == nums[i-1]){//不可以越界i++;}}return ret;}
}

4.四數之和(難度:🔴5度)

題目描述

給你一個由 n 個整數組成的數組 nums ，和一個目標值 target 。請你找出并返回滿足下述全部條件且不重復的四元組 [nums[a], nums[b], nums[c], nums[d]] （若兩個四元組元素一一對應，則認為兩個四元組重復）：
0 <= a, b, c, d < n
a、b、c 和 d 互不相同
nums[a] + nums[b] + nums[c] + nums[d] == target
你可以按任意順序返回答案。
示例 1：
輸入：nums = [1,0,-1,0,-2,2], target = 0
輸出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
示例 2：
輸入：nums = [2,2,2,2,2], target = 8
輸出：[[2,2,2,2]]

算法原理
a. 依次固定?個數a ；
b. 在這個數a 的后?區間上，利?「三數之和」找到三個數，使這三個數的和等于target -a 即可。
代碼編寫

class Solution {public List<List<Integer>> fourSum(int[] nums, int target) {List<List<Integer>> ret = new ArrayList<>();Arrays.sort(nums);for (int i = 0; i < nums.length;){for (int j = i+1;j < nums.length;){int left = j+1;int right = nums.length-1;long t = (long)target-nums[j]-nums[i];while(left < right){if (nums[left] + nums[right] == t){List<Integer> a = new ArrayList<>();a.add(nums[left]);a.add(nums[right]);a.add(nums[j]);a.add(nums[i]);ret.add(a);left++;right--;while(left < nums.length && nums[left] == nums[left-1]){left++;}while(right > 0 && nums[right] == nums[right+1]){right--;}}else if(nums[left] + nums[right] < t){left++;}else{right--;}}j++;while(j < nums.length && nums[j] == nums[j-1]){j++;}}i++;while(i < nums.length && nums[i] == nums[i-1]){i++;}}return ret;}
}