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: The solution set must not contain duplicate triplets.
1 2 3 4 5 6 7 8 9 10
> > For example, given array S = [-1, 0, 1, 2, -1, -4], > > > > A solution set is: > > [ > > [-1, 0, 1], > > [-1, -1, 2] > > ] > > > >
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32
class {public : vector <vector <int >> threeSum(vector <int >& nums) { int len = nums.size(); sort(nums.begin(), nums.end()); int findNum; vector <vector <int >>::iterator iter; vector <vector <int >> res; for (int i = 0 ; i < len - 2 ; ++i) { if (nums[i] > 0 ) return res; for (int j = i + 1 ; j < len - 1 ; ++j) { findNum = 0 - nums[i] - nums[j]; if (findNum < 0 ) break ; if (binary_search(nums.begin() + j + 1 , nums.end(), findNum)) { vector <int > v; v.push_back(nums[i]); v.push_back(nums[j]); v.push_back(findNum); iter = std ::find(res.begin(), res.end(), v); if (iter == res.end()) res.push_back(v); } } } return res; } };
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47
class {public : vector <vector <int >> threeSum(vector <int > &nums) { int len = nums.size(); int j, k, sum; vector <vector <int >> res; sort(nums.begin(), nums.end()); for (int i = 0 ; i < len - 2 ; ++i) { if (i == 0 || nums[i] != nums[i - 1 ]) { j = i + 1 ; k = len - 1 ; sum = 0 - nums[i]; while (j < k) { if (nums[j] + nums[k] == sum) { vector <int > v; v.push_back(nums[i]); v.push_back(nums[j++]); v.push_back(nums[k--]); res.push_back(v); while (j < k && nums[j] == nums[j - 1 ]) j++; while (j < k && nums[k] == nums[k + 1 ]) k--; } else if (nums[j] + nums[k] > sum) { k--; } else { j++; } } } } return res; } };
近期评论