LeetcodeHot100（6）三数之和

一、题目分析：

给定一个整数数组nums，需要找到所有不重复的三元组(a, b, c)，满足：

1. a + b + c = 0；
2. 三元组中三个元素的下标互不相同；
3. 结果中不能包含重复的三元组（例如[-1,0,1]和[0,-1,1]视为同一个三元组，只保留一份）

二.核心思路：排序法+双指针法

不能使用暴力枚举法，时间复杂度为o（n3次方）太复杂。

先对数组进行一个从小到大的排序；相同的数字挨着，方便重复使用。

然后固定一个数a，然后a的下一个定义为左指针second 来找b，最后一个元素定义为右指针third 来找c。目标找到 b+c = -a；

然后固定第一个数为a，计算 b+c是否等于-a。如果b+c>-a，则结果偏大，把右指针左移来减小数。如果b+c<-a，结果偏小，把左指针右移来增大数。

直到b+c = -a时候，把a和b、c提出来，然后跳过和b、c重复的元素 继续寻找。

直到左右指针重合了，那么就让a移到下一个。继续找。遇到重复的a也跳过。

直到某个a开始大于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; //容器ans 存放一个整数容器 //枚举a for(int first = 0; first < n; ++first){ //如果a是相同的得跳过，所以必须和上一次枚举的不同 if(first > 0 && nums[first] == nums[first - 1]){ continue;//如果a和上一次的a一样，就跳过此次循环 } //c对应最右 int third = n-1; int target = -nums[first]; //枚举b for(int second = first +1;second < n ;++second){//second是a的下一个数 if(second>first+1 && nums[second] == nums[second-1]){ continue;//如果b和上一次的b一样 也跳过 } //保证b在c的左侧 while(second < third && nums[second] + nums[third]>target){ --third; //如果三者的和大于零 就左移右指针 减小数值 } //如果指针重合 跳出循环 if(second == third){ break; } //满足的记录下来 if(nums[second]+nums[third] == target){ ans.push_back({nums[first],nums[second],nums[third]}); } } } return ans; } };

class Solution { public: vector<vector<int>> threeSum(vector<int>& nums) { //左右指针法 a+b+c = 0； sort(nums.begin(),nums.end()); int n = nums.size(); vector<vector<int>> ans; for(int left = 0;left<n;left++){ //判断一下和上一个相等吗 if(left>0&&nums[left-1]==nums[left]) continue; int target = -nums[left]; int b = left +1; int c = n-1; //b c的初始位置 while(b<c){ if(b > left+1 && nums[b] == nums[b-1]) { b++; continue; } if(c < n-1 && nums[c] == nums[c+1]) { c--; continue; } if(nums[b]+nums[c] < target){ b++; } else if(nums[b]+nums[c]>target){ c--; } else { //满足条件 存起来 ans.push_back({nums[left],nums[b],nums[c]}); // b去重：跳过所有和当前b相等的数 //while(b < c && nums[b] == nums[b+1]) b++; // c去重：跳过所有和当前c相等的数 // while(b < c && nums[c] == nums[c-1]) c--; //收缩 b++; c--; } } } return ans; } };