首页 > 代码库 > 3Sum

3Sum

2024-07-21 12:27:38   213人阅读

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)

思路：

 1 class Solution { 2 public: 3     vector<vector<int> > threeSum( vector<int> &num ) { 4         vector<vector<int> > triplets; 5         sort( num.begin(), num.end() ); 6         int size = num.size(); 7         vector<int> triplet( 3, -1 ); 8         for( int i = 0; i < size-2; ++i ) { 9             if( i > 0 && num[i] == num[i-1] ) { continue; }10             if( num[i] > 0 ) { break; }11             int s = i+1, e = size-1;12             while( s < e ) {13                 if( num[e] < 0 ) { break; }14                 if( s > i+1 && num[s] == num[s-1] ) { ++s; continue; }15                 if( e < size-1 && num[e] == num[e+1] ) { --e; continue; }16                 int sum = num[i] + num[s] + num[e];17                 if( sum == 0 ) {18                     triplet[0] = num[i];19                     triplet[1] = num[s];20                     triplet[2] = num[e];21                     triplets.push_back( triplet );22                     ++s; --e;23                 } else if( sum < 0 ) {24                     ++s;25                 } else {26                     --e;27                 }28             }29             30         }31         return triplets;32     }33 };

 

3Sum


联系
我们