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)
大体的思想先将数组排序，从小到大取vector中的数first，再从剩下的数中取和等于 0 - first 的数即可。下面是代码（一开始没想出来，然后参考了别人的解法在写出来，一般的三层循环谁都能想到，但是时间复杂度太高，这里的这个时间复杂度应该是O（N^2）,还是可以接受的）
1 class Solution { 2 public: 3 vector<vector<int>> threeSum(vector<int>& nums) 4 { 5 vector<vector<int>> result; 6 int sz = nums.size(); 7 sort(nums.begin(), nums.end()); 8 for (int i = 0; i < sz - 2; ++i){ 9 twoSum(nums, i + 1, 0 - nums[i], result); 10 while(nums[i] == nums[i + 1]) ++i;//这一步要注意，防止得出重复的vector 11 } 12 return result; 13 } 14 15 void twoSum(vector<int> & nums, int start, int value, vector<vector<int>> & ret) 16 { 17 int beg = start; 18 int end = nums.size()-1; 19 while (beg < end){ 20 int sum = nums[beg] + nums[end]; 21 if (sum < value) 22 beg++; 23 else if (sum > value) 24 end--; 25 else{ 26 ret.push_back(vector<int>{nums[start - 1], nums[beg], nums[end]}); 27 while (nums[beg + 1] == nums[beg]) beg++;//这一步的处理应该注意，防止出现相同的vector 28 while (nums[end - 1] == nums[end]) end--; 29 beg++, end--; 30 } 31 } 32 } 33 };
原文：http://www.cnblogs.com/-wang-cheng/p/4856282.html