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)
华丽的分割线,刷OJ真的是磨练一个人的事情。。。。。。。。。。。。。。
class Solution { public: vector<vector> threeSum(vector& nums) { vector<vector>result; if (nums.size() < 3) return vector<vector>{}; sort(nums.begin(), nums.end()); //去重复 for (int i = 0; i < nums.size() - 2; i++) { if(i > 0 && nums[i] == nums[i-1])continue;//重复的元素不用计算 int target2 = 0 - nums[i]; twosum(i+1, target2, nums,result); } return result; } void twosum(int start, int target, vector& nums, vector<vector>&result) { int first = start; int second = nums.size()-1; while (first < second) { int k = nums[first] + nums[second]; if (k < target) { first++; } else if (k > target) { second--; } else { result.push_back(vector{nums[start-1], nums[first], nums[second]}); //为了防止出现重复的二元组,使结果等于target int tmp = first + 1; while (tmp< second && nums[tmp] == nums[first]) { tmp++; } first = tmp; tmp = second - 1; while (tmp > first && nums[tmp] == nums[second]) { tmp--; } second = tmp; } } } };