class Solution {
public:
void quick_order(vector<int>& num, int star, int en)//快排
{
int start = star;
int end = en;
if (start >= end)
return;
int index = num[start];//就第一个设为阈值
while (start < end)
{
while (start < end && index <= num[end])//先看右边，把第一个小于index数找出
end--;
int temp1 = num[start];//交换
num[start] = num[end];
num[end] = temp1;
while (start < end && index >= num[start])//再看右边，把第一个大于index的数找出
start++;
int temp2 = num[start];//交换
num[start] = num[end];
num[end] = temp2;
}
quick_order(num, star, start-);//分左右子集迭代
quick_order(num, start + , en);
return;
}
vector<vector<int>> threeSum(vector<int>& nums) {
int len=nums.size();
vector<vector<int>> res;
if(len==)//输入判断
return res;
int start=,end=len-;
quick_order(nums,start,end);//快排
vector<vector<int>> v2;
for (int c = nums.size()-; c >= ; ){
for (int a = , b = c-; a < b; ){
int tmp_sum = nums[a]+nums[b];
if (tmp_sum < -nums[c]){
++a;
} else if (tmp_sum > -nums[c]){
--b;
} else {
vector<int> v = {nums[a], nums[b], nums[c]};
v2.push_back(v);
do{//去重复 a b
++a;
} while (a < b && nums[a-] == nums[a]);
do{
--b;
} while (a < b && nums[b+] == nums[b]);
}
}
do{//去重复 c
--c;
} while (c >= && nums[c+] == nums[c]);
}
return v2;
/*for(int fir=1;fir<len-1;fir++)
{
int sec=fir-1,thr=fir+1;
while(sec>=0 && thr<=len-1)
{
int sum=nums[fir]+nums[sec]+nums[thr];
if (sum==0)
{
vector<int> node={nums[sec],nums[fir],nums[thr]};
bool flag=true;
for(int i=0;i<res.size();i++)
{
if(node==res[i])
flag=!flag;
}
if(flag)
res.push_back(node);
sec = sec - 1;
}
else if (sum>0)
sec=sec-1;
else if (sum<0)
thr=thr+1;
}
}
return res;*/
}
};分析：
不写代码永远不知道自己有多菜，一个快排写的我哭了，然后说主要思想：
未注释的是别人的代码，排序后，令【a，。。。。，b，c】这种形式，让c从右往左遍历，a初始化为0，从左向右移动，b初始化c-1，从右往左移动。在c遍历中，计算a+b，若a+b<-c，说明a太小了，a++，若a+b>-c，说明b大了，b--。最让我值得学习的是去重复，其实不难，就是a，b，c在各自道路上有重复就前进。
注释的是我自己的想法，排序后，令【。。。a，b，c，。。。】这种形式，b从左向右遍历，a初始化b-1，从b往左移动，c初始化b+1，从b往右移动。在b遍历中，计算a+c，若a+b+c>0，a--，若a+b+c<0，b++。这里已经实现了除去重复所有功能，且时间复杂度和上面一样，但是就在去重复这里我懵了，我先按查找已被选择的三数，但是碰到一个变态长的数组，时间复杂度蹭蹭的上涨，然后我就分析重复情况，有两个例子【-1，0，0，1】和【-2，-1，-1，0，1，2】，一个是【【-1，0，1】】，一个是【【-1，-1，2】，【-1，0，1】】，这里面如果你让b跳过重复的，那就错过后面案例的【-1，-1，2】，如果不跳过，前面案例就会重复，搞的我又一点点分析，但是真的好难写，难写在于解决一个情况，但是又有新的情况，二者特矛盾，有一没二那种，后来代码越写越长，还丑，我就只能捂着脸学习别人的思想了。
下次再碰到想到中间指针时候，想想指针从后向前或从前向后的情况。