【leetcode】3Sum

3Sum

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)

先对数组进行排序，从头开始扫描，扫描的数作为固定的数。

a=num[i];

当固定了一个数以后，

选取b=num[i+1]=num[j]

选取c=num[n-1]=num[k]

若a+b+c=0

则找到了一个a，b，c，记录下来，j++,k--继续扫描

若a+b+c<0

则j++

若a+b+c>0

则k--

要注意去重的问题：

1.若num[i]=num[i-1]，则跳过

2.若num[j]=num[j-1]，则跳过

3.若num[k]=num[k+1]，则跳过

 1 class Solution {
 2 public:
 3     vector<vector<int> > threeSum(vector<int> &num) {
 4        
 5         int n=num.size();
 6         sort(num.begin(),num.end());
 7        
 8         int i,j,k;
 9         int a,b,c;
10         vector<vector<int> > result;
11        
12         for(i=0;i<n-2;i++)
13         {
14             j=i+1;
15             k=n-1;
16            
17             while(j<k)
18             {
19                 a=num[i];
20                 if(i>0&&num[i]==num[i-1])
21                 {
22                     break;
23                 }
24                 b=num[j];
25                 if(j>i+1&&num[j]==num[j-1])
26                 {
27                     j++;
28                     continue;
29                 }
30                
31                 c=num[k];
32                 if(k<n-1&&num[k]==num[k+1])
33                 {
34                     k--;
35                     continue;
36                 }
37                
38                 if(a+b+c==0)
39                 {
40                     vector<int> tmp(3);
41                     tmp[0]=a;
42                     tmp[1]=b;
43                     tmp[2]=c;
44                     result.push_back(tmp);
45                     j++;
46                     k--;
47                 }
48                 else if(a+b+c<0)
49                 {
50                     j++;
51                 }
52                 else if(a+b+c>0)
53                 {
54                     k--;
55                 }
56             }
57         }
58        
59         return result;
60        
61     }
62 };
63