原文鏈接：15. 三數之和 - 力扣（LeetCode）

思路解析

雙指針：

? ? ? ? （1）頭尾指針對應值相加如果大于目標值(target)，那么只能尾指針-1；如果小于target，那么只能頭指針+1。

? ? ? ? （2）如何去除重復？因為已經排好序了，如果下一個要檢索的值等于前一個檢索的值，直接跳過。

    public List<List<Integer>> threeSum(int[] nums) {/*** 雙指針：* 頭指針：開始指向當前元素的下一個元素* 尾指針：開始指向最后一個元素*/Arrays.sort(nums);int len = nums.length;List<List<Integer>> ans = new ArrayList<>();for (int i = 0; i < nums.length; i++) {if (i > 0 && nums[i] == nums[i - 1]) continue;int j = i + 1;int k = len - 1;int x = nums[i];while(j<k){int result = x+nums[j]+nums[k];if(result>0){k--;}else if(result<0){j++;}else {ans.add(Arrays.asList(x,nums[j],nums[k]));j++;//繼續排查當前遍歷的i，還有沒有別的組合while(nums[j]==nums[j-1] && j<k){j++;}k--;while(nums[k]==nums[k+1] && j<k){k--;}}}}return ans;}

---

兩個優化：

????????優化1：如果最小的三個值相加都大于0，那么沒有滿足要求 的，直接break

????????優化2：如果當前值和最大的兩個值相加都小于0，那么本次遍歷的i沒有滿足要求的，直接continue

    public List<List<Integer>> threeSum(int[] nums) {Arrays.sort(nums);int len = nums.length;List<List<Integer>> ans = new ArrayList<>();for (int i = 0; i < nums.length; i++) {if (i > 0 && nums[i] == nums[i - 1]) continue;int j = i + 1;int k = len - 1;int x = nums[i];if(x+nums[j]+nums[j+1] > 0) break;//優化1if(x+nums[k]+nums[k-1] < 0) continue;//優化2while(j<k){int result = x+nums[j]+nums[k];if(result>0){k--;}else if(result<0){j++;}else {ans.add(Arrays.asList(x,nums[j],nums[k]));j++;//繼續排查當前遍歷的i，還有沒有別的組合while(nums[j]==nums[j-1] && j<k){j++;}k--;while(nums[k]==nums[k+1] && j<k){k--;}}}}return ans;}

---

同樣的思路，會做這一題，你就會兩數之和了，兩數之和也是用這個思想，更簡單

1. 兩數之和 - 力扣（LeetCode）

?