目錄
查找總價格為目標值的兩個商品
暴力解題
雙指針解題
三數之和
雙指針解題(左右指針)
四數之和
雙指針解題
雙指針關鍵點
注意事項
查找總價格為目標值的兩個商品
題目鏈接：LCR 179. 查找總價格為目標值的兩個商品 - 力扣（LeetCode）
題目描述：
輸??個遞增排序的數組和?個數字 s ，在數組中查找兩個數，使得它們的和正好是 s 。如果有多
對數字的和等于 s ，則輸出任意?對即可。
?例 1：
輸?： nums = [2,7,11,15], target = 9
輸出： [2,7] 或者 [7,2]
暴力解題
class Solution {public static int[] twoSum(int[] price, int target) {int n=price.length;int[] array=new int[2];for(int i=0;i<n;i++){for(int j=i+1;j<n;j++){if(price[i]+price[j]==target){array[0]=price[i];array[1]=price[j];return array;}}}return array;}
}雙指針解題
解題思路：由于數組是升序的，我們可以使用【左右指針】，left和right指針分別指向最小值和最大值，判斷其和是否等于目標值target。相等的話則直接返回，結束遍歷
如果不相等，有兩種情況：
·和小于target：采取增大最小值，逐漸接近target。即left++
·和大于target：采取減小最大值，逐漸接近target。即right--
解題代碼：
class Solution {public static int[] twoSum(int[] price, int target) {int[] array=new int[2];int n=price.length;int left=0;int right=n-1;while(left<right){int sum=price[left]+price[right];if(sum>target){right--;}else if(sum<target){left++;}else{array[0]=price[left];array[1]=price[right];return array;}}return array;}
}三數之和
題目鏈接：15. 三數之和 - 力扣（LeetCode）
題目描述：
給你?個整數數組 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 。
提?：
3 <= nums.length <= 3000
-10^5 <= nums[i] <= 10^5
雙指針解題(左右指針)
題目分析：我們需要在數組中，找到滿足 和為0且不重復?的三元組
重點：不重復
解題思路：既然是三元組，我們選擇固定一個元素temp，然后只需找到 【和為-temp的二元組】 即可
1.排序，并且固定最大值(假設下標為i)：因為如果不排序，隨機固定一個元素，無法使用雙指針找到 【和為-nums[i]的二元組】。
2.找到 【和為-temp的二元組】:使用【左右指針】，left指針指向0，right指針指向?i?左側的位置
如下圖：
本題如何保證【不重復】呢？
·在找到一個【二元組】后，left和right指針需要【跳過重復】的元素：首先需要先跳過已找到的【二元組】，即left++，right--。其次，如果新的left、right處的元素與上一個【二元組】的數相同，也需要跳過。
·當使用完一次雙指針算法后，固定的i也要【跳過重復】的元素：即當left和right指針相遇后，i--之后(for循環實現)，如果新的i處的元素與前一個i處的元素相等，需要額外的i--
假設最大值的下標為i，區間[left,right]是i位置左邊的區間--也就是比i小的區間：
如果nums[left]+nums[right]>-nums[i]:這時需要減小【較大值】(right--)，嘗試接近-nums[i]
如果nums[left]+nums[right]<-nums[i]:這時需要增大【較小值】(left++)，嘗試接近-nums[i]
優化：在尋找三數之和為0時，當三個數中最大的那個數小于0時，三數之和只能小于0。
解題代碼：
class Solution {public static List<List<Integer>> threeSum(int[] nums) {List<List<Integer>> arr=new ArrayList<>();Arrays.sort(nums);int n=nums.length-1;for(int i=n;i>=2;i--){if(nums[i]<0) break;int left=0;int right=i-1;while(left<right){int sum=nums[left]+nums[right];int target=-1*nums[i];if(sum>target){right--;}else if(sum<target){left++;}else{arr.add(new ArrayList<Integer>(Arrays.asList(nums[i],nums[left],nums[right])));left++;right--;while(left < right && nums[left] == nums[left - 1]) left++;while(left < right && nums[right] == nums[right + 1])right--;}}while(i>2&&nums[i]==nums[i-1])i--;}return arr;}
}四數之和
題目鏈接：18. 四數之和 - 力扣（LeetCode）
題目描述：
給你?個由 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]]
提?：
1 <= nums.length <= 200
-10^9 <= nums[i] <= 10^9
-10^9 <= target <= 10^9
題目分析：我們需要在數組中，找到滿足 和為target且不重復?的四元組
重點：不重復(解決方法與三數之和類似，這里不進行闡述)
雙指針解題
解題思路：與三數之和類似。由于這里是【四元組】，我們選擇固定兩個元素。然后 只需使用【左右指針】，找到一個【二元組】使其與固定的兩個元素之和等于目標值(target)即可。
注意：由于?-10^9 <= nums[i] <= 10^9,當nums[i]+nums[j]+nums[left]+nums[right]時，這里可能會導致超出int類型的最大值，所以需要強制類型轉換為(long)
解題代碼：
class Solution {
public static List<List<Integer>> fourSum(int[] nums, int target) {List<List<Integer>> arr=new ArrayList<>();Arrays.sort(nums);int n=nums.length;//固定一個最小值和一個最大值for(int i=0;i<n;i++){//去重while(i<n&&i!=0&&nums[i]==nums[i-1]) i++;for(int j=n-1;j>i;j--){//去重while(j>i&&j!=n-1&&nums[j]==nums[j+1]) j--;int left=i+1;int right=j-1;while(left<right){long sum=(long)nums[i]+nums[j]+nums[left]+nums[right];if(sum==target){arr.add(Arrays.asList(nums[i],nums[j],nums[left],nums[right]));left++;right--;//去重while(left<right&&nums[left]==nums[left-1]) left++;while(left<right&&nums[right]==nums[right+1]) right--;}else if(sum>target){right--;}else{left++;}}}}return arr;}
}雙指針關鍵點
1.初始化
通常，雙指針被初始化為指向數據結構(如數組)的開始和結束，或者根據問題的具體要求進行其他初始化
2.移動規則
指針的移動規則取決于要解決的問題。例如，在尋找有序數組中的兩數之和(如本章的第一題)時，如果當前兩數之和小于目標值，則左指針右移以增加和；如果大于目標值，則右指針左移以減小和
3.停止條件
當指針相遇或交叉，或者滿足問題的特定條件時，遍歷結束
4.空間復雜度
雙指針技術通常具有O(1)的額外空間復雜度，因為它只需要維護兩個指針的位置，而不需要額外的數據結構來存儲數據
注意事項
1.邊界條件：在使用雙指針時，要特別注意邊界條件，確保指針不會越界或指向無效的位置
2.指針的同步移動：根據問題的要求，指針可能需要同步移動(如同時向右移動)，或者按照特定的規則異步移動(如一個指針固定，另一個指針移動)
3.問題的轉化：有時，將問題轉化為可以使用雙指針技術解決的形式才是關鍵。例如，通過排序將無序數組轉化為有序數組，從而可以應用雙指針技術。
)