t*****t
发帖数: 285 | 1 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)
class Solution {
private:
int increment(vector& nums, int l, int r){
while(l
return l;
}
int decrement(vector& nums, int l, int r){
while(r>l && nums[r]==nums[--r]){}
return r;
}
public:
vector> threeSum(vector& nums) {
vector> res;
if(nums.size()<3) return res;
sort(nums.begin(), nums.end());
for(int i=0; i
int l = i+1;
int r = nums.size()-1;
while(l
if(nums[i]+nums[l]+nums[r] == 0){
vector tmp {nums[i], nums[l], nums[r]};
res.push_back(tmp);
l = this->increment(nums,l,r);
r = this->decrement(nums,l,r);
}
else if(nums[i]+nums[l]+nums[r] < 0){
l = this->increment(nums,l,r);
}
else{
r = this->decrement(nums,l,r);
}
}
}
return res;
}
}; | u**l
发帖数: 35 | 2 class Solution {
public:
vector> threeSum(vector& nums) {
vector> ret;
if (nums.size() < 3) {
return ret;
}
sort(nums.begin(), nums.end());
for (int i = 0; i < nums.size() - 2; ++i) {
if (i > 0 && nums.at(i) == nums.at(i - 1)) {
continue;
}
twoSum(ret, i + 1, nums, 0 - nums.at(i));
}
return ret;
}
private:
void twoSum(vector>& res, int index, vector& sortedNums
, int target) {
int head = index;
int tail = sortedNums.size() - 1;
while (head < tail) {
int tmp = sortedNums.at(head) + sortedNums.at(tail);
if (tmp < target) {
++head;
}
else if (tmp > target) {
--tail;
}
else {
vector v;
v.push_back(sortedNums.at(index - 1));
v.push_back(sortedNums.at(head));
v.push_back(sortedNums.at(tail));
res.push_back(v);
int k = head + 1;
while (k < tail && sortedNums.at(k) == sortedNums.at(head)) {
++k;
}
head = k;
k = tail - 1;
while (k > head && sortedNums.at(k) == sortedNums.at(tail)) {
--k;
}
tail = k;
}
}
}
}; | t*****t
发帖数: 285 | |
|
