三數之和(雙指針)

題意：
給你一個包含 n 個整數的數組 nums，判斷 nums 中是否存在三個元素 a，b，c ，使得 a + b + c = 0 ？請你找出所有滿足條件且不重復的三元組。

注意：答案中不可以包含重復的三元組。

示例：

給定數組 nums = [-1, 0, 1, 2, -1, -4]，
滿足要求的三元組集合為：
[
[-1, 0, 1],
[-1, -1, 2]
]

分析：
從數值的分析上，a+b+c=0一定有數字大于等于0，有數值小于等于0，如果無序，那么暴力枚舉各個數O(n3)并且還需要考慮去重。

可以采取動靜的思路，首先對序列進行排序，三個數字，一個在左面，一個在左面，一個在右面，三個中以其中一個為定點，如果以中間為臨時定，左右兩個分別從兩邊向中間指針試探，如果其中遇到相等的即加入結果集。但是這樣的一個結果需要去重，因為無法判斷唯一，具體實現代碼為：

public List<List<Integer>> threeSum(int[] nums) {List<List<Integer>> list=new ArrayList<List<Integer>>();Set<String>set=new HashSet<String>();Arrays.sort(nums);for(int i=1;i<nums.length-1;i++){ int left=0;int right=nums.length-1;while (left<i&&right>i) {//System.out.println(i+" "+left+" "+i+" "+right+" "+list.toString());if(nums[left]>0)break;int sum=nums[left]+nums[i]+nums[right];//System.out.println(nums[left]+" "+nums[i]+" "+nums[right]);if(sum==0){String teamString=nums[left]+" "+nums[i]+" "+nums[right];if(!set.contains(teamString)) {List<Integer>list2=new ArrayList<Integer>();list2.add(nums[left]);list2.add(nums[i]);list2.add(nums[right]);list.add(list2);set.add(teamString);}left++;right--;}else if (sum>0) {right--;}else {left++;}}}return list; }

而如果循環一次每次確定左側的，中間的和右側的分別向右側和左側拓展，那么這樣可以實現一個去重，并且時間復雜度為O(n2)但需要注意以下細節：

• 當前最左側數字sums[i]如果和sums[i-1]（i>1）相等，那么跳出本次計算，因為當前數字如果作為最左側數字那么前面有相同的數字可以組成這個集合，所以不需要這部的計算。
• 同時在確定最左側，中間left和最右側right向中間進行時如果三數之和大于0，那么right–；如果三數之和小于0，那么left++；同時你可以進行部分剪枝優化，把不可能的情況直接過濾掉。

ac代碼為：

public List<List<Integer>> threeSum(int[] nums) {List<List<Integer>> list=new ArrayList<List<Integer>>();Arrays.sort(nums);for(int i=0;i<nums.length-2;i++){ int left=i+1;int right=nums.length-1;if(i>0&&nums[i]==nums[i-1])continue;while (left<right) {//System.out.println(i+" "+left+" "+i+" "+right+" "+list.toString());if(nums[left]+nums[i]>0)break;int sum=nums[left]+nums[i]+nums[right];//System.out.println(nums[left]+" "+nums[i]+" "+nums[right]);if(sum==0){List<Integer>list2=new ArrayList<Integer>();list2.add(nums[i]);while (left<right&&nums[left]==nums[left+1]) {left++;}list2.add(nums[left]);while (left<right&&nums[right]==nums[right-1]) {right--;}list2.add(nums[right]);list.add(list2);left++;right--;} else if (sum>0) {right--;}else {left++;}}}return list;}

最接近的三數之和

題意：
給定一個包括 n 個整數的數組 nums 和 一個目標值 target。找出 nums 中的三個整數，使得它們的和與 target 最接近。返回這三個數的和。假定每組輸入只存在唯一答案。

示例：

輸入：nums = [-1,2,1,-4], target = 1
輸出：2
解釋：與 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。

提示：

3 <= nums.length <= 10^3
-10^3 <= nums[i] <= 10^3
-10^4 <= target <= 10^4

分析:
有了上題的思路，本題依然使用雙指針，不過最接近sum需要你用數字記錄它的大小并且還需要考慮正負的問題。

具體的處理上，和上一題整體思想一致，首先排序，循環一次確定最左側的,這層為O(n),同時每個最左側確定之和中間和右側分別向中間靠攏，如果三數之和大于target，那么right–，否則left++，同時要和最接近的數進行比較是否更接近，這樣執行完畢即可獲得最接近target的三個數字之和。

具體實現代碼為：

public static int threeSumClosest(int[] nums, int target) { Arrays.sort(nums);int value=nums[0]+nums[1]+nums[2];for(int i=0;i<nums.length-2;i++){ int left=i+1;int right=nums.length-1;while (left<right) {int sum=nums[left]+nums[i]+nums[right];int gap1=Math.abs(value-target);int gap2=Math.abs(sum-target);if(target>=0&&nums[left]+nums[i]-target>gap1)break;if(gap2<gap1){value=sum;} if (sum==target) {return target;}else if(sum>target) {right--;}else {left++;} }}return value;}

結語

原創不易，bigsai請你幫兩件事幫忙一下:

star支持一下， 您的肯定是我在平臺創作的源源動力。

微信搜索「bigsai」，關注我的公眾號，不僅免費送你電子書，我還會第一時間在公眾號分享知識技術。加我還可拉你進力扣打卡群一起打卡LeetCode。

記得關注、咱們下次再見！

總結

以上是生活随笔為你收集整理的LeetCode 15三数之和16最接近的三数之和的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。