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: int b_search(vector<int> &n, int b, int e, int x) { int l = b; int r = e; while (l <= r) { int mid = l + ((r - l ) >> 2); if (n[mid] == x) { return mid; } else if (n[mid] > x) { r = mid - 1; } else { l = mid + 1; } } return -1; } /* *固定其中2点,找第3点,如果找到就添加到结果中 * 每次固定左边的点,从右想走遍历右边的点,查找两个点的之间是否有满足的点 * 注意左边的点要去掉重复的 */ vector<vector<int>> threeSum(vector<int>& nums) { int i,j,k; int size = nums.size(); vector<vector<int>> res; sort(nums.begin(), nums.end()); for (i=0; i<size-2; i++) { //过滤掉相同的左边点,防止出现重复的结果 if (i > 0 && nums[i] == nums[i-1]) { continue; } for (j=size-1; j>i+1; j--) { if (j < size-1 && nums[j] == nums[j+1]) { continue; } int s = b_search(nums, i+1, j-1, 0 - nums[i] - nums[j]); if (s != -1) { vector<int> tmp; tmp.push_back(nums[i]); tmp.push_back(nums[s]); tmp.push_back(nums[j]); res.push_back(tmp); } } } return res; } };
原文：http://www.cnblogs.com/SpeakSoftlyLove/p/5097467.html