一、简单分析
题目的输出：输出的顺序和三元组的顺序不重要。也就是可能出现重复结果，需要消重。
例如，从题目给的示例1中，正常全排列的方式能够得到3个结果，但是其中2个结果是重复的。
那么本题既然三元组的顺序不管，那么就可以使用排列。
排列后，只有出现 最左边有负值，最右边有正值的情况，才有机会三数之和为0；
以下都是不对的：
- 左负，右负
- 左正，右正
从而想到左边加上右边后，离0值还差多远。而这个差值，则遍历去寻找。
二、算法逻辑
1）设左值针 left = i+1，右指针 right = n-1
2）如果 num[i] + num[left] + num[right] = 0，就保存这三个三元组。
3）如果 num[i] + num[left] + num[right] > 0，说明 num[right] 大了，那么 right 指针左移。
4）如果 num[i] + num[left] + num[right] < 0，说明 num[left] 小了，那么 left 指针右移动。
5）左右指针在移动的时候，需要判断和下个位置的值是否重合。重复了，就继续移动。
6）这左右指针的相对位置不能改变，改变就可以退出了。
三、代码逻辑
具体在代码中实现时，由于是从左往右遍历，就省略 （4） 的判断了
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
//排序
//二维数组保存输出
//遍历指针
//和上一次枚举的数不同
//右指针初始成最右端
//左指针比遍历指针后一个位置
//和上一次枚举的数不同
//左指针在右指针左边
//如果三和大于0,右指针左移
//指针重合就退出循环
//如果三和等于0,存入二维数组中
//返回二维数组
}
};完整代码
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
int n = nums.size();
//排序
sort(nums.begin(), nums.end());
//二维数组保存输出
vector<vector<int>> ans;
//遍历指针
for(int i = 0; i < n; i++){
//和上一次枚举的数不同,否则继续右移
if(i > 0 && nums[i] == nums[i - 1]){
continue;
}
//右指针初始成最右端
int right = n - 1;
int target = -nums[i];
//左指针比遍历指针后一个位置
for (int left = i + 1; left < n; left++){
//和上一次枚举的数不同
if( left > i + 1 && nums[left] == nums[left -1 ])
continue;
//左指针在右指针左边
while(left < right && nums[left] + nums[right] > target){
//如果三和大于0,右指针左移
right --;
}
//指针重合就退出循环
if(left == right)
break;
//如果三和等于0,存入二维数组中
if( nums[left] + nums[right] == target)
ans.push_back({nums[i], nums[left], nums[right]});
}
}
//返回二维数组
return ans;
}
};