LeetCode第十五题3Sum思路

题目：

Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note:The solution set must not contain duplicate triplets.

Example:Given array nums = [-1, 0, 1, 2, -1, -4],A solution set is:[[-1, 0, 1],[-1, -1, 2]]

一眼看这个题目感觉还行啊，于是无脑穷举遍历。

代码如下： 

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<int>::iterator iter,iter2,iter3;
        vector <vector<int> >::iterator iter4; 
        int i,a,b,c,k;
        vector<vector<int>> res;
        if(nums.size()<3)
            return res;
        sort(nums.begin(),nums.end());
        k=0;
        for(iter=nums.begin();iter!=(nums.end()-2);++iter)
        {
            for(iter2=(iter+1);iter2!=(nums.end()-1);++iter2)
            {
                for(iter3=(iter2+1);iter3!=nums.end();++iter3)
                {
                    vector<int> res1;
                    if((*iter+*iter2+*iter3)==0)
                    {
                            res1.push_back(*iter);
                            res1.push_back(*iter2);
                            res1.push_back(*iter3);
                            res.push_back(res1);
                            k++;
                    }
                }
            }
        }
        //去重
	    sort(res.begin(),res.end());
        for(iter4=res.begin();iter4!=res.end();)
        {
            if(*iter4==*(iter4+1))
            {
                res.erase(iter4);
            }else{
                iter4++;   
            }
        }
        return res;
    }
};

 想着数据量好像也不大啊，没啥毛病啊，可能是我写的太low了。（三个循环肯定超时）

 于是只能想着用别的办法了。

 想象下一个数组中，找两个数，他们的和为0，那么可以表示为a+b=0，一般用两个循环就可以解决了，（当然还有更加高效的解法，这里就不引申了），那么三个数呢？题目中三个数是这样表达的a+b+c=0,那是不是可以变换下等式，a+b=-c,这样一来我们可以先找到两个数的组合，然后匹配第三个数，这样一来就可以用两个循环解决了，时间复杂度上就降了很多，从原来的,就变成了。那么具体要怎么实现能？我下面简单说明下思路。

首先当然是对这个数组进行排序处理，这样有什么好处呢？排序处理后我们就可以从数组当中首位开始取数，一个个往后找，可以避免很多重复的，对重复的数可以直接跳过，同时在找第三个数c的时候也可以按顺序往前找，可以减少很多操作。

然后第一重循环可以先找数组中的第一个数nums[0]作为a，然后nums[0+1]作为b。那么第二重循环，可以找第三个数了，这样两个循环就能解决问题了，但是第三个数从哪里开始找呢？

 看上面这张图，既然a和b都是复数，并且这两个数是整个数组中最小的，那么它们俩相加的值是不是也是所有数中的两个数相加和最小的呢？答案是肯定的，那么后面c就要取一个最大的数来相加了，这样结果才可能等于0，数组已经排好序了，这样我们就可以从数组中从后往前找了，最后一个数肯定是最大的，这就是前面为什么排序的原因之一了。

 这里分别用i，j，k，来控制a，b，c的下标移动。

那么如上图所示一开始可以取a=nums[i],b=nums[j]  (j=i+1),c=nums[len-1]  (len=nums.size())

然后第一重循环可以控制i的移动，第二重循环可以控制j和k的移动。

首先i取0的时候，j取1，k取len-1 （第一重循环）

（下面是第二重循环）

1.然后判断a+b是否小于-c，如果a+b小于-c了，那么这种情况c的下标k就不需要往前移了，再往前移c只会越来越小。所以这里就直接b的下标往后移一个j++,如上图这个时候j就是在2这个位置了，然后再继续从最后找c。

2.再判断a+b是否大于-c，如果a+b大于-c，那么c的下标k就往前移找一个更小的，直到a+b=-c，如果找不到那就结束，继续找下个b

3.最后一个判断a+b是否等于-c，如果a+b等于-c，那么结果就是需要找的这个-c，然后就把这三个数存到vector中去。

关键步骤就结束了，但是在第二个循环开始之前还是可以再做点优化的，比如第一个数=,这种情况可以直接跳过，因为和前面那个数重复了，后面都是做重复的操作。还有当>0的时候，这里就可以直接结束整个遍历了，因为一个排好序的数组，不可能三个大于0的整数相加等于0的，所以直接结束。

下面贴上代码：

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> res;
        if(nums.size()<3)
            return res;
        sort(nums.begin(),nums.end());
        for(int i=0,len=nums.size();i<len;i++)
        {
            if(nums[i]<=0)
            if(i==0||nums[i]>nums[i-1]){
            int j=i+1;
            int k=len-1;
            while(j<k)
            {
                vector<int> res1;
                if(nums[i]+nums[j]+nums[k]<0){
                    j++;
                }else if(nums[i]+nums[j]+nums[k]>0){
                    k--;
                }else{
                    res1.push_back(nums[i]);
                    res1.push_back(nums[j]);
                    res1.push_back(nums[k]);
                    res.push_back(res1);
                    j++;
                    k--;
                }
            }
            }
        }
        //去重
        vector<vector<int>>::iterator iter;
	    sort(res.begin(),res.end());
        for(iter=res.begin();iter!=res.end();)
        {
            if(*iter==*(iter+1))
            {
                res.erase(iter);
            }else{
                iter++;   
            }
        }
        return res;
    }
};