讨论下leetcode 3sum

这道题我写了个这样的解法：

1. vector<vector<int> > threeSum(vector<int> &num) {
   
2.         // Start typing your C/C++ solution below
   
3.         // DO NOT write int main() function
   
4.         vector<vector<int> > result;
   
5.          int i = 0, j = i + 1, l = num.size() - 1;
   
6.          if(l<2) return result;
   
7. 
   
8.         sort(num.begin(), num.end());
   
9.         int prev1 = num[0];
   
10.         int prev2 = num[1];
    
11.         int prev3 = num[2];
    
12.         
    
13.         for(i = 0; i < num.size() - 2; i++)  
    
14.         {   if(i>0&&prev1 == num[i]) continue;
    
15.             int a = num[i];
    
16.             prev1 = num[i];
    
17.             prev2 = num[i+1];
    
18.             prev3 = num[num.size()-1];
    
19.             for(j = i + 1, l = num.size() - 1; j < l; )  
    
20.             {   if(j>i+1&&prev2 == num[j]) {
    
21.                     j++;
    
22.                     continue;
    
23.                 }
    
24.                 if(l<num.size()-1&&prev3 == num[l]){
    
25.                     l--;
    
26.                     continue;
    
27.                 }
    
28.                
    
29.                 int b = num[j];  
    
30.                 int c = num[l];  
    
31.                 if(a + b + c < 0)  
    
32.                 {  
    
33.                     j++;  
    
34.                 }  
    
35.                 else if(a + b + c > 0)  
    
36.                 {   
    
37.                     l--;  
    
38.                 }  
    
39.                 else  
    
40.                 {  
    
41.                     vector<int> v;
    
42.                     v.push_back(a);
    
43.                     v.push_back(b);
    
44.                     v.push_back(c);
    
45.                     result.push_back(v);
    
46.                      prev2 = num[j];
    
47.                      prev3 = num[l];
    
48.                      j++;
    
49.                      l--;
    
50.                     continue;
    
51.                 }  
    
52.             }  
    
53.         }  
    
54.         return result;  
    
55.     }

复制代码

还有更快的解法吗？ 求牛牛们指点！

不会有多少区别吧。先排序，然后对每一个位置：取左右两个点，根据其和进行移动。
遍历位置为O(n)，移动左右点累积移动也是O(n)，所以时间复杂度为O(n^2)
总的时间复杂度为O(nlgn) + O(n^2)=O(n^2)
ps.代码排版不好啊。。

1. #include <iostream>
   
2. #include <algorithm>
   
3. #include <vector>
   
4. using namespace std;
   
5. 
   
6. class Solution {
   
7. public:
   
8.     vector<vector<int> > threeSum(vector<int> &num) {
   
9.         // Start typing your C/C++ solution below
   
10.         // DO NOT write int main() function
    
11.         vector<vector<int> > res;
    
12.         sort(num.begin(), num.end());
    
13.         int len = num.size();
    
14.         for(int i = 0; i <= len - 3; ++i)
    
15.         {
    
16.             while(i > 0 && i <= len - 3 && num[i] == num[i - 1])
    
17.                 ++i;
    
18.             if(i > len - 3)
    
19.                 break;
    
20.             int l = i + 1;
    
21.             int h = len - 1;
    
22.             while(l < h)
    
23.            {
    
24.                int sum = num[i] + num[l] + num[h];
    
25.                if(sum == 0)
    
26.               {
    
27.                    vector<int> com;
    
28.                    com.push_back(num[i]);
    
29.                    com.push_back(num[l]);
    
30.                    com.push_back(num[h]);
    
31.                    res.push_back(com);
    
32.                    l++;
    
33.                    while(l < h && num[l] == num[l - 1])
    
34.                          l++;
    
35.                    h--;
    
36.                    while(l < h && num[h] == num[h + 1])
    
37.                          h--;
    
38.               }
    
39.              else if(sum < 0)
    
40.             {
    
41.                  l++;
    
42.                 while(l < h && num[l] == num[l - 1])
    
43.                     l++;
    
44.              }
    
45.              else
    
46.            {
    
47.                 h--;
    
48.                 while(l < h && num[h] == num[h + 1])
    
49.                 h--;
    
50.            }
    
51.       }
    
52.             }
    
53.         return res;

复制代码

tiger 发表于 2013-1-9 13:32
不会有多少区别吧。先排序，然后对每一个位置：取左右两个点，根据其和进行移动。
遍历位置为O(n)，移动左 ...

恩，咱俩方法好像一样的

tiger 发表于 2013-1-9 13:32
不会有多少区别吧。先排序，然后对每一个位置：取左右两个点，根据其和进行移动。
遍历位置为O(n)，移动左 ...

恩，咱俩方法好像一样的