一、題目描述

15.?三數之和

給你一個整數數組?nums?，判斷是否存在三元組?[nums[i], nums[j], nums[k]]?滿足?i != j、i != k?且?j != k?，同時還滿足?nums[i] + nums[j] + nums[k] == 0?。請

你返回所有和為?0?且不重復的三元組。

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

注意重復表示每個元素不能一一對應

二、題目解析

算法思想：排序+雙指針

思路：

1. 先排序
2. 固定一個數a；
3. 在該數后面的區間內，利用“雙指針算法”快速找到兩個的和等于-a即可。

處理細節問題：

1、去重

• 找到一種結果之后，left和right指針要跳過重復元素
• 當使用完一次雙指針算法之后，i也需要跳過重復元素

2、不漏

找到一種結果之后，不要“停”，縮小空間，繼續尋找

三、原碼

class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {vector<vector<int>> ret;//1、排序sort(nums.begin(),nums.end());//2、利用雙指針解決for(int i = 0;i<nums.size();){int left = i+1;int right = nums.size()-1;int target = -nums[i];while(left < right){if(nums[left] + nums[right] > target)right--;else if(nums[left] + nums[right] < target)left++;else{ret.push_back({nums[i],nums[left],nums[right]});left++;right--;//去重left和rightwhile(left<right && nums[left] == nums[left-1]) left++;while(left<right && nums[right] == nums[right+1]) right--;}}//去重ii++;while(i<nums.size() && nums[i] == nums[i-1]) i++;}return ret;}
};