LeetCode OJ--3Sum **

http://oj.leetcode.com/problems/3sum/

找出三个数的和是0的元组.

class Solution {
public:
      vector<vector<int> > threeSum(vector<int> &num) {
        vector<vector<int> > ans;
        
        if(num.size()<3)
            return ans;

        sort(num.begin(),num.end()); // 排序处理
        for(int i = 0;i<num.size()-2;i++)
        {
             
            for(int j = i+1;j<num.size()-1;j++)
            {
                if(num[i] + num[j] >0)
                        break;
                if(num[i]+num[j]+num[num.size()-1]<0)
                    continue;
                for(int k = j+1;k<num.size();k++)
                {
                    if(num[i]+num[j]+num[k]==0)
                    {
                        vector<int> onePiece;
                        onePiece.push_back(num[i]);
                        onePiece.push_back(num[j]);
                        onePiece.push_back(num[k]);
                        int flag = 0;
                        for(int t = 0;t<ans.size();t++)
                        {
                            if(num[i] == ans[t][0] && num[j]== ans[t][1] && num[k] == ans[t][2])
                            {
                                flag = 1;
                                break;
                            }
                        }
                        if(flag == 0)
                            ans.push_back(onePiece);
                        break;
                    }
                    if(num[i]+num[j]+num[k]>0)
                        break;
                }
                
            }
        }
        return ans;
    }
};

尽管加上了各种剪枝，还是超时，于是参考了别人的代码。

 vector<vector<int> > threeSum(vector<int> &num) {
        vector<vector<int> > ans;
        
        if(num.size()<3)
            return ans;

        sort(num.begin(),num.end()); // 排序处理

        vector<int> onePiece;
        for(int i = 0;i<num.size()-2;i++)
        { 
            int j = i+1;
            int k = num.size()-1;
            while(j<k)
            {
                if(num[i]+num[j]+num[k]>0)
                    k--;
                else if(num[i]+num[j]+num[k]<0)
                    j++;
                else
                {
                    onePiece.clear();
                    onePiece.push_back(num[i]);
                    onePiece.push_back(num[j]);
                    onePiece.push_back(num[k]);
                    ans.push_back( onePiece);
                    j++;
                    k--;
                    
                }
            }
        }
        ans.erase(unique(ans.begin(),ans.end()),ans.end());
        return ans;
    }

这样固定 i 之后，同时调整 j k 在思路上清晰，效果也确实好，复杂度为 O(n²).

但是运行结果为  Output Limit Exceeded