3Sum

Given an array S of n integers, are there elements abc 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)
C++:
01 bool compare(int i, int j)
02 {
03     return i<j;
04 }
05 class Solution {
06 public:
07     vector<vector<int> > threeSum(vector<int> &num) {
08         // Start typing your C/C++ solution below
09         // DO NOT write int main() function
10         sort(num.begin(), num.end(), compare);
11         vector<vector<int>> result;
12         int n=num.size();
13         for(int i=0;i<n2😉
14         {
15             int j=i+1;
16             int k=n1;
17             while(j<k)
18             {
19                 if(num[i]+num[j]+num[k]==0)
20                 {
21                     vector<int> item;
22                     item.push_back(num[i]);
23                     item.push_back(num[j]);
24                     item.push_back(num[k]);
25                     result.push_back(item);
26                     j++;
27                     while((j<k)&&(num[j]==num[j1]))
28                     {
29                         j++;
30                     }
31                 }
32                 else if(num[i]+num[j]+num[k]<0)
33                 {
34                     j++;
35                 }
36                 else
37                 {
38                     k;
39                 }
40             }
41             i++;
42             while((num[i]==num[i1])&&(i<n2))
43             {
44                 i++;
45             }
46         }
47         return result;
48     }
49 };
Advertisements
This entry was posted in Array and linked list. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s