这个题确实比較复杂。我刚刚開始的思路是先将数组排序，然后从左向右遍历。然后用两个变量lpos，rpos分别指向left+1
和 nums.size()-1，然后求三者的和。若和sum < 0 则让lpos加1，若sum>0则让rpos减1。想法不错。但是现实非常残酷。
这样
的解非常easy错过真实解。我測试了非常多遍，总有測试用例无法通过。
当中另一个时间复杂度太高了也没通过測试。这个题大家
能够自己去实现试试，真的错误点太多了，最后还是採用了比較老实的办法，再一步一步分析，求的解例如以下:
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
//三数之和为0，至少一个数小于0，至少一个数大于0 排序之后从两边向中间遍历
vector<vector<int>> last;
int len = nums.size();
if (len < 3)
{
return last;
}
//1.排序
sort(nums.begin(), nums.end());
/*
for (int i = 1; i<len; ++i)
{//插入排序时间复杂度为O(n^2),所以还是用vector自带的排序
int tmp = nums[i];
int begin = i - 1;
while (begin >= 0 && nums[begin] > tmp)
{
nums[begin + 1] = nums[begin];
--begin;
}
nums[begin + 1] = tmp;
}
*/
//2.从两边向中间遍历，最左边的数字加上最右边的数字。然后找数字中和他们的和
for (int left = 0; left < len - 2 && nums[left] <=0 ; ++left)
{
if(left > 0 && nums[left] == nums[left-1])
{//left 和 left-1 位置元素相等，可是第一次不能处理
continue;
}
int lpos = left + 1;
int rpos = 0;
while (lpos < len-1)
{ //尝试了好多次，实验结果证明lpos和rpos不能从两边向中间遍历，++lpos和--rpos的究竟谁先运行无法确定，所以还得像暴力求解那样
if(lpos != left+1 && nums[lpos] == nums[lpos-1])
{//说明了此时left+1相应的值已经求出值了，须要处理掉同样的lpos值
++lpos;
continue;
}
rpos = lpos+1;
while (lpos < rpos && nums[left] + nums[lpos] + nums[rpos] <= 0)
{
if (lpos < rpos && nums[left] + nums[lpos] + nums[rpos] == 0)
{
vector<int> tmp;
tmp.push_back(nums[left]);
tmp.push_back(nums[lpos]);
tmp.push_back(nums[rpos]);
last.push_back(tmp);
break; //处理完后跳出本次循环
}
else if(rpos < len-1)
{
++rpos;
}
else
{
break;
}
}
++lpos; //运行到这里不要忘记了改变lpos的值，否则可能死循环
}
}
return last;
}
};
上面的代码中有一定凝视，希望能够帮助大家看懂求解思路，我总结一下此题须要注意的地方吧，这些都是我出现过的:
1. 不能出现反复的解。那么我们须要在每次求出一个解后将反复的元素过滤掉同样的left。lpos，rpos值。处理这样的情况
非常easy出错。代码必须非常慎重
2. 须要非常细致的处理。否则总有一千种測试用例让你的代码无法通过，一般就是你改了代码。满足了第一个測试用却无法
满足第二个，当你再次改掉代码满足第二个測试用例。你会发现第一个用无法通过了，简直要崩溃了。
3. lpos，rpos的处理不当就会导致死循环，这时候会提示你超时了。
4. 一个left值可能会有好几个解，所以须要让lpos和rpos遍历完 left~ nums.size()-1 整个序列
5. 尽管这个题对于某些大神来说不难，可是无论怎么样还是须要測试一个。不试不知道，一试吓一跳。
6. 想到的思路却又无法解答此题的时候不要"死想"。能够换种方式去解题
最后的结果是通过的，希望写LeetCode的人都提供正确答案。否则没有意义。
