原题

Given an array S of n integers, are there elements abc 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.

```For example, given array S = [-1, 0, 1, 2, -1, -4],

A solution set is:
[
[-1, 0, 1],
[-1, -1, 2]
]
```

题解

two-pointes solution

[code lang=”cpp”]
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector< vector<int> > rs;
int l = nums.size();
sort(nums.begin(), nums.end());

for (int i = 0; i < l – 2; ++i) {
int f = i + 1, b = l – 1;
if (i – 1 >= 0 && nums[i] == nums[i – 1]) continue;
while (f < b) { if (nums[f] + nums[b] > -nums[i]) {
while(nums[b] == nums[–b]) {}
} else if (nums[f] + nums[b] < -nums[i]) {
while(nums[f] == nums[++f]) {}
} else {
vector<int> tmp = {nums[i], nums[f], nums[b]};
rs.push_back(tmp);
while(nums[b] == nums[–b]) {}
while(nums[f] == nums[++f]) {}
}
}
}

return rs;
}
};
[/code]

Share:

This site uses Akismet to reduce spam. Learn how your comment data is processed.