# 15. 3Sum 三数之和

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]
]
``````

### 解法1

``````class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> res;
sort(nums.begin(),nums.end());
for (int k = 0;k < nums.size();k++)
{
//因为排序了, 到k>0时候应该结束
if (nums[k] > 0) break;
//排除相同数字
if (k > 0 && nums[k]==nums[k-1]) continue;
//转换成求两个数之和等于target
int target = 0 - nums[k];
int i = k + 1,j = nums.size()-1;
while (i < j)
{
if (nums[i]+nums[j] == target)
{
res.push_back({nums[k],nums[i],nums[j]});
while (i<j && nums[i]==nums[i+1]) i++;
while (i<j && nums[j]==nums[j-1]) j--;
i++;
j--;
}
else if (nums[i]+nums[j]<target) i++;
else j--;
}
}
return res;
}
};
``````

### 解法2

``````class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
set<vector<int>> res;
sort(nums.begin(), nums.end());
for (int k = 0; k < nums.size(); ++k) {
if (nums[k] > 0) break;
int target = 0 - nums[k];
int i = k + 1, j = nums.size() - 1;
while (i < j) {
if (nums[i] + nums[j] == target) {
res.insert({nums[k], nums[i], nums[j]});
while (i < j && nums[i] == nums[i + 1]) ++i;
while (i < j && nums[j] == nums[j - 1]) --j;
++i; --j;
} else if (nums[i] + nums[j] < target) ++i;
else --j;
}
}
return vector<vector<int>>(res.begin(), res.end());
}
};
``````