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> > res; 5 if(num.size() < 3) 6 return res; 7 sort(num.begin(), num.end()); 8 int N = num.size(); 9 for(int i = N-1; i >= 2; i--) { 10 if(i != N-1 && num[i] == num[i+1]) { 11 continue; } // handle duplicated cases 12 for(int j = 0, k = i-1; j < k; ) { 13 if(j != 0 && num[j] == num[j-1]) { j++; continue; } 14 if(k != i-1 && num[k] == num[k+1]) { k--; continue; } 15 int sum = num[i] + num[j] + num[k]; 16 if(sum == 0) { 17 vector<int> tmp(3); 18 tmp[0] = num[j]; 19 tmp[1] = num[k]; 20 tmp[2] = num[i]; 21 res.push_back(tmp); 22 j++; 23 k--; 24 } 25 else if(sum < 0) { j++; } 26 else { k--; } 27 } 28 } 29 return res; 30 } 31 };
原文：http://www.cnblogs.com/zhengjiankang/p/3644610.html