15. 三数之和

一、简单分析

题目的输出：输出的顺序和三元组的顺序不重要。也就是可能出现重复结果，需要消重。

例如，从题目给的示例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; }
};