前言
多少人夢想開始的地方，兩數之和。
但是今天要聊的不是入門第一題，也沒有面試官會考這一題吧…不會真有吧？
咳咳不管有沒有，今天的豬腳是它的兄弟，三數之和，作為雙指針經典題目之一，也是常常作為面試常考題出現。今天就來和大家分析分析這題的詳細解法和雙指針題目的思路。
三數之和
題目鏈接：15. 三數之和
示例 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] 。
注意，輸出的順序和三元組的順序并不重要。
初始代碼：
var threeSum = function(nums) {
};
解題思路
看完了題目，這題的重點是：
- 數組是無序的
- 不能有重復的答案
- 每個答案數組都需要進行記錄，同時i!=j,j!=k，
那么先開始思考：
- 暴力是否可以得出答案，答案是可以的。好下課- ??(?????)！，咳咳但是由于暴力時間復雜度為O(n)^3所以鐵定是超時的
- 那么接下就是是否能進行優化，暴力是會具有大量的重復查詢，我們需要做的是消除重復查詢并且縮短查詢時間
- 消除重復查詢的辦法，我選擇的是對數組先進行排序。這樣相同的元素放在一起，可以防止重復查詢。
- 縮短查詢時間，我選擇的是雙指針，既然是雙指針，那么必須需要固定好一個數，才能讓雙指針進行移動。這里我選擇的是固定第一個數字，第二個數字為左指針指向第一個數字后的一位數，第三個數字為右指針指向數組末尾的數。下面是例圖：
因為數組是已經排好了序，所以我們只需要把這題當作一下問題求解即可：
當給你一個數target，讓你在一個有序數組中找到兩個數和為(-target)的所有解,并且解不能相同。是不是感覺特別簡單。從三個數的尋找直接變成了兩個數求和 ，那么接下來就來開始做題。
做題步驟
下面是偽代碼，大家可以看著能不能寫出來??(?? ? ??)??
var threeSum = function(nums) {
//1- 首先定義一個返回的結果數組，result//2- 對數組進行排序//3- 排好序之和就進行數組遍歷
//數組遍歷從下標0開始，先遍歷第一個數的范圍（arr.length-3）,因為三數之和必須需要三個數
// 所以第一個數的下標范圍為 0-length-3//4- 第一個數被固定后，需要進行雙指針遍歷剩余的數，但是在遍歷之前我們需要進行去除
//重復元素的操作，就是判斷第一個數為target時候是否已經查詢過結果，如果查詢過就直接跳過//5-去重之后，就定義雙指針一個指向第一個數之后，一個指向數組末尾,定義一個數記錄三數之和，方便我
//們移動雙指針//6-我們這里需要循環判斷，壓縮數組的空間，來找到所有符合的答案，所以這里我們需要while循環
//直到條件為左指針>=右指針下標時結束尋找//7-如果答案符合我們需要進行記錄，并且，第二個數和第三個數也需要進行去除重復元素的操作//8- 結束循環返回result數組
};
正式代碼：
var threeSum = function(nums) {
//1- 首先定義一個返回的結果數組，resultconst result = [];//2- 對數組進行排序nums.sort((a,b)=>a-b);//3- 排好序之和就進行數組遍歷
//數組遍歷從下標0開始，先遍歷第一個數的范圍（arr.length-3）,因為三數之和必須需要三個數
//所以第一個數的下標范圍為 0-length-3for(let i=0,len=nums.length;i<=len-3;i++){//4- 第一個數被固定后，需要進行雙指針遍歷剩余的數，但是在遍歷之前我們需要進行去除
//重復元素的操作，就是判斷第一個數為target時候是否已經查詢過結果，如果查詢過就直接跳過,如果第一
//數大于0，那么也無需進行遍歷直接返回即可因為數組是排好序的。第一個數都大于0，那么三數之和不可能為0if(nums[i]>0)return result;if(i!=0&&nums[i]==nums[i-1]){continue;}//5-去重之后，就定義雙指針一個指向第一個數之后，一個指向數組末尾,定義一個數記錄三數之和，方便我
//們移動雙指針let sum =0;let left = i+1;let right = len-1;//6-我們這里需要循環判斷，壓縮數組的空間，來找到所有符合的答案，所以這里我們需要while循環
//直到條件為左指針>=右指針下標時結束尋找while(left<right){sum =nums[i]+nums[left]+nums[right];//7-如果答案符合我們需要進行記錄，并且，第二個數和第三個數也需要進行去除重復元素的操作if(sum==0){result.push([nums[i],nums[left],nums[right]])while(left<right&&nums[left]==nums[left+1]){left++;}while(right>left&&nums[right]==nums[right-1]){right--;}left++;right--;}else if(sum>0){right--;}else{left++;}}//8- 結束循環返回result數組}return result;
}
可以看到效率還是非常不錯的，那么本題的分享到此結束。
謝謝大家的觀看，喜歡的話可以點個關注或者是點贊，謝謝- ??(?????)。
)
