15. 三數(shù)之和

難度中等5841

給你一個整數(shù)數(shù)組?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

• -105?<= nums[i] <= 105

通過次數(shù)1,330,456提交次數(shù)3,606,941

思路：

尋找元素->哈希法（但我不會寫，明天寫這種方法）

雙指針：

第一種對法：

class?Solution?{

public:

????vector<vector<int>>?threeSum(vector<int>&?nums)?{

????????int?left,right;

????????vector<vector<int>>ans;

????????sort(nums.begin(),nums.end());

????????for(int?i=0;i<nums.size();i++){

????????????if(nums[i]>0)return?ans;

????????????if(i>0&&nums[i]==nums[i-1])continue;

????????????left?=?i+1;

????????????right?=?nums.size()-1;

????????????while(left<right){

????????????????if(nums[i]+nums[left]+nums[right]>0)right--;

????????????????else?if(nums[i]+nums[left]+nums[right]<0)left++;

????????????????else{

????????????????????ans.push_back(vector<int>{nums[i],nums[left],nums[right]});

????????????????????while(right>left&&nums[left]==nums[left+1])left++;

????????????????????while(right>left&&nums[right]==nums[right-1])right--;

????????????????????left++;right--;

????????????????}

????????????????

????????????}

????????}

????????return?ans;???

????}

};

細節(jié)：

1. 雙指針法要將數(shù)組排序

2. 題目中要去重

3. 對i去重時要讓去重條件為nums[i]==nums[i-1]而不是nums[i]==nums[i+1],因為i+1為left這樣會導致像-1,-1,2這種答案不能被取到

4. 選擇left與right的循環(huán)條件只能是left<right不能是left<=right若是第二種寫法的話就會讓left和right取到同一個值

5. right和left的去重要在取到一個正確答案的代碼后面去重，不然會出現(xiàn)漏取的情況，并且left要嚴格小于right

6. 記得在循環(huán)的后面讓left,right加加減減，不然就是死循環(huán)

7. 因為數(shù)組已經(jīng)排序，所以當nums[i]>0時就不會再有正確答案出現(xiàn)，就可以直接將ans這個二維數(shù)組返回