Leetcode 15 3sum

1.题目要求

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

Note:

Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c)
The solution set must not contain duplicate triplets.

    For example, given array S = {-1 0 1 2 -1 -4},

    A solution set is:
    (-1, 0, 1)
    (-1, -1, 2)

2.分析

第一想法，三层循环。简单直接，复杂度O（n^3），代码如下：

 1 class Solution {
 2 public:
 3     vector<vector<int> > threeSum(vector<int> &num) {
 4         int lenght = num.size();
 5         int i,j,k;
 6         vector<vector<int> > result;
 7         result.clear();
 8         vector<int> temp;
 9 
10         for (i=0;i<lenght;i++)
11         {
12             temp.clear();
13             for (j=i+1;j<lenght;j++)
14             {
15                 for(k=j+1;k<lenght;k++)
16                     if (0 == num[i]+num[j]+num[k])
17                     {
18                         temp.push_back(num[i]);
19                         temp.push_back(num[j]);
20                         temp.push_back(num[k]);
21                         sort(temp.begin(),temp.end());
22                         result.push_back(temp);
23                     }
24             }
25         }
26         return result;
27 
28     }
29 };

提交结果不想而知：Time Limit Exceeded。

在翻阅以前的Leetcode题目中，有一道题和该题很相似，就是Leetcode 1题，其复杂度为O（n），这道题是在vector中寻找满足a+b=target的下标，因此，我们可以将本题要求变换为a+b=-c，直接调用1题代码，其代码如下：

注意：在调用代码时需要做一些小小的修改。

  1 class mySolution {
  2 public:
  3     vector<int> twoSum(vector<int> &numbers, int target) {
  4         vector<int> result;
  5         result.clear();
  6         map<int,int> myMap;
  7 
  8         int i,temp;
  9         int length = numbers.size();
 10         map<int,int>::iterator it;
 11         myMap.insert(pair<int,int>(numbers[0],0));
 12         for (i=1;i<length;i++)
 13         {
 14             temp = target - numbers[i];
 15             it = myMap.find(temp);
 16             if (it!=myMap.end())
 17             {
 18                 result.push_back(it->second+1);
 19                 result.push_back(i+1);
 20             }
 21             myMap.insert(pair<int,int>(numbers[i],i));
 22         }
 23         //cout << result[0] << " " << result[1]<<endl;
 24         return result;
 25 
 26     }
 27 
 28 };
 29 
 30 class Solution {
 31 public:
 32     vector<vector<int> > threeSum(vector<int> &num) {
 33         int lenght = num.size();
 34         int i,j,k,l;
 35         vector<vector<int> > result;
 36         vector<vector<int> >::iterator it1;
 37         result.clear();
 38         vector<int> temp;
 39         vector<int> temp1;
 40         vector<int> temp2;
 41         vector<int>::iterator it;
 42         mySolution obj;
 43         set<int> mySet;
 44         mySet.clear();
 45         
 46 
 47 
 48         for (i=0;i<lenght;i++)
 49         {
 50             temp1 = num;//为了保证num的完整性，故做这一步操作
 51             it = temp1.begin();
 52             temp1.erase(it+i);//删除num[i]是为了避免num[i]被选中两次
 53             if (mySet.find(num[i]) == mySet.end())
 54             {
 55                 mySet.insert(num[i]);
 56                 temp = obj.twoSum(temp1,0-num[i]);
 57             }else
 58                 continue;;
 59             int mysize = temp.size();
 60             if (0==mysize)
 61             {
 62                 continue;
 63             }
 64             else
 65             {
 66                 l=0;
 67                 while (mysize)
 68                 {
 69                     j=temp[l]-1;
 70                     k=temp[l+1]-1;
 71                     mysize--;
 72                     mysize--;
 73                     l+=2;
 74                     temp2.clear();
 75                     temp2.push_back(temp1[j]);
 76                     temp2.push_back(temp1[k]);
 77                     temp2.push_back(num[i]);
 78                     sort(temp2.begin(),temp2.end());
 79 
 80                     for (it1=result.begin();it1!=result.end();it1++)
 81                     {
 82                         if ((*it1)==temp2)
 83                         {
 84                             break;
 85                         }
 86                     }
 87                     if (it1 == result.end())
 88                     {
 89                         result.push_back(temp2);
 90                     }
 91                 }        
 92                 
 93                 
 94             }
 95 
 96             
 97         }
 98         return result;
 99 
100     }
101 };

提交：Time Limit Exceeded。呵呵，看来还是不行啊。得想更好的办法了。

第二个代码中时间复杂度是O（n^2），执行结果是Time Limit Exceeded。因此需要考虑时间复杂度为O（nlgn）--->想到排序。

有了这个思路，重新设计算法。

算法大致思路：先将vector排序，然后遍历vector，当 a=a[i] 时后面的问题就是 : a[i+1] 到 a[n-1]中 b+c =-a （编程之美 2.12 快速寻找满足条件的两个数）

记 b=a[j]=a[i-1] c=a[k]=a[n-1]

若 b+c < -a ，j++;

b+c > -a ，j--;

b+c=-a 记录下来，并j++;

代码如下：

class Solution {
public:
    vector<vector<int> > threeSum(vector<int> &num) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
       
        vector<vector<int> > ret;
         ret.clear();
        sort(num.begin(),num.end());
        for(int i=0; i!=num.size();i++){
            if(i > 0 && num[i]==num[i-1])
                continue;
            int j,k;
            j=i+1;
            k=num.size()-1;
            while(j<k){
                if(j>i+1&&num[j]==num[j-1]){ 
                    j++;
                    continue;
                }
                if(k<num.size()-1&& num[k]==num[k+1]){
                    k--;
                    continue;
                }
                 int sum = num[i] + num[j] + num[k];
                if(sum>0){
                    k--;
                }else if(sum<0){
                    j++;
                }else{
                    vector<int> tmp;
                    tmp.push_back(num[i]);
                    tmp.push_back(num[j]);
                    tmp.push_back(num[k]);
                    ret.push_back(tmp);
                    j++;
                }
            }
        }
        return ret;
            
    }
};

最后提交。Accepted。