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.
For example, given array S = [-1, 0, 1, 2, -1, -4],
A solution set is:
[
[-1, 0, 1],
[-1, -1, 2]
]
解题思路
这道题是之前的Two Sum题的升级版，不同的是Two Sum要求返回的是数组的下标，而本题要求返回的是数组元素本身。大体思路如下：
- 对数组进行排序
- 遍历数组，将每次遍历变成一个Two Sum的问题，注意需要跳过重复的数字
- 由于数据已经排序，解决Two Sum问题的时候，可以直接使用两个下标从数组头尾分别开始扫描。假设数组为nums, 头尾下标分别为beg和end, 若nums[beg] + nums[end] > target,则end--, 否则beg++。
具体代码如下所示：
class Solution
{
vector<vector<int>> threeSum(vector<int>& nums) {
sort(nums.begin(),nums.end());
vector<vector<int>> res;
int target = 0;
for(int i = 0; i < nums.size(); ++i)
{
if(nums[i] > 0) break; //如果第一个数字>0, 直接返回。
if(i > 0 && nums[i] == nums[i-1]) continue; //数字重复，直接跳出本次循环
int l = i+1 , r= nums.size() - 1;
target = 0 - nums[i];
while(l < r)
{
if(nums[l] + nums[r] > target)
r--;
else if(nums[l] + nums[r] < target)
l++;
else{
res.push_back({nums[i],nums[l],nums[r]});
while(l < r && nums[l] == nums[l + 1]) l++;
while(l < r && nums[r] == nums[r - 1]) r--;
l++; r--;
}
}
}
return res;
}
}
思路二：
根据网上大神的解法，可以采用set不能包含重复项的特点来防止重复项的产生。具体代码如下：
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
sort(nums.begin(),nums.end());
set<vector<int>> res;
int target = 0;
for(int i = 0; i < nums.size(); ++i)
{
if(nums[i] > 0) break;
int l = i+1 , r= nums.size() - 1;
target = 0 - nums[i];
while(l < r)
{
if(nums[l] + nums[r] > target)
r--;
else if(nums[l] + nums[r] < target)
l++;
else{
res.insert({nums[i],nums[l],nums[r]});
l++; r--;
}
}
}
return vector<vector<int>>(res.begin(),res.end());
}
};
