题目：
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:
For example, given array S = {-1 0 1 2 -1 -4},
A solution set is:
(-1, 0, 1)
(-1, -1, 2)
代码：
class Solution { public: vector<vector<int> > threeSum(vector<int> &num) { std::vector<std::vector<int> > ret_vector; if (num.size() < 3) { return ret_vector; } // sort the vector std::sort(num.begin(), num.end()); // visit all the left side element of the current element const int target = 0; std::vector<int>::iterator end = num.end(); for (std::vector<int>::iterator i = num.begin(); i != end-2; ++i){ // ignore first duplicate i if ( i > num.begin() && *i==*(i-1)) continue; std::vector<int>::iterator j = i+1; std::vector<int>::iterator k = end-1; while (j<k){ const int tmp = *i+*j+*k; if ( tmp < target ){ ++j; while ( *j==*(j-1) && j<k ) ++j; } else if ( tmp > target ){ --k; while ( *k==*(k+1) && j<k ) --k; } else{ int tmp_triple[3] = {*i,*j,*k}; std::vector<int> tmp_vector(tmp_triple,tmp_triple+3); ret_vector.push_back(tmp_vector); ++j; --k; while( *j==*(j-1) && *k==*(k+1) && j<k ) { ++j; --k; } } } } return ret_vector; } };
Tips:
1. 先对传入的vector排序，然后从前向后遍历。原则是：包含*i元素，且满足条件的triple都加入到返回结果中
2. 这里比较困难的一点是排除重复的triple，大概想一想原则，一些极端的case只能试验出来了
另，在mac上编辑的，不知道为什么用数组初始化vector编译不通过，所以采用了比较麻烦的传参方式
原文：http://www.cnblogs.com/xbf9xbf/p/4439240.html