笔试题28. LeetCode OJ (15)

　　这个题确实比较复杂，我刚刚开始的思路是先将数组排序，然后从左向右遍历，然后用两个变量lpos，rpos分别指向left+1

　　和 nums.size()-1，然后求三者的和，若和sum < 0 则让lpos加1，若sum>0则让rpos减1。想法不错，可是现实很残酷。这样

　　的解很容易错过真实解，我测试了很多遍，总有测试用例无法通过。其中还有一个时间复杂度太高了也没通过测试。这个题大家

　　可以自己去实现试试，真的错误点太多了，最后还是采用了比较老实的办法，再一步一步分析，求的解如下:

　　　　class Solution {

　　public:

　　vector<>> threeSum(vector& nums) {

　　//三数之和为0，至少一个数小于0，至少一个数大于0 排序之后从两边向中间遍历

　　vector<>> last;

　　int len = nums.size();

　　if (len < 3)

　　{

　　return last;

　　}

　　//1.排序

　　sort(nums.begin(), nums.end());

　　/*

　　for (int i = 1; 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 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值，处理这种情况

　　很容易出错，代码必须很谨慎

　　2. 需要很仔细的处理，否则总有一千种测试用例让你的代码无法通过，一般就是你改了代码，满足了第一个测试用却无法

　　满足第二个，当你再次改掉代码满足第二个测试用例，你会发现第一个用无法通过了，简直要崩溃了。

　　3. lpos，rpos的处理不当就会导致死循环，这时候会提示你超时了。

　　4. 一个left值可能会有好几个解，所以需要让lpos和rpos遍历完 left~ nums.size()-1 整个序列

　　5. 虽然这个题对于某些大神来说不难，但是不管怎么样还是需要测试一个，不试不知道，一试吓一跳。

　　6. 想到的思路却又无法解答此题的时候不要"死想"，可以换种方式去解题

　　最后的结果是通过的，希望写LeetCode的人都提供正确答案，否则没有意义。