题目

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请

你返回所有和为 0 且不重复的三元组。

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

思路

为保证不重复，给数组排个序，遍历时同一个位置跳过遍历过的数。选定一个数x，另外两个数和则应为-x。由于数组是递增的求首尾之和，若结果大于-x，则右边界往左移，小于则左边界往右移，等于则两侧同时收缩。 里面两层循环优化证明：给出一组递增数列 a b c d e f.若 a+f>0,则x（x属于{b c d e})+f必定大于0，f肯定不会构成符合要求的组合，淘汰f。若a+f<0,则a+y(y属于{b,c,d,e})必定小于0，a必定不会构成符合要求的组合。a+f=0,因为不能出现重复的组合，三个数之和确定两个数则第三个数也是确定的，让a往右收缩一位到b，a+f=0,b>a,=>b+f>0,所以f也得收缩一位。

代码

class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {vector<vector<int> >list;int len=nums.size();vector<int>x;sort(nums.begin(),nums.end());int a=0x3f3f3f,cnt=0;for(int i=0;i<len-2;i++){if(nums[i]==a){continue;}else{a=nums[i];}int b=0x3f3f3f,k=len-1,c=nums[k];for(int j=i+1;j<len-1;){if(j>=k){break;}int sum=nums[i]+nums[j]+nums[k];if(sum==0){x.clear();x.push_back(nums[i]);x.push_back(nums[j]);x.push_back(nums[k]);list.push_back(x);while(c==nums[k]&&k>j){k--;}c=nums[k];}else if(sum>0){while(c==nums[k]&&k>j){k--;}c=nums[k];}else{while(b==nums[j]&&j<k){j++;}b=nums[j];}}}return list;}
};