3sum一道非常经典的题目，第一次做，以前只做了2Sum，老规矩先上暴力破解解法：
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
int n = nums.size();
sort(nums.begin(),nums.end());
set<vector<int>> result;
vector<vector<int>> res;
for(int i = 0;i < n - 2;i++)
{
for(int j = i + 1;j < n -1;j++)
{
for(int k = j + 1;k < n;k++)
{
if(nums[i] + nums[j] + nums[k] != 0)
continue;
vector<int> zero{nums[i],nums[j],nums[k]};
if (result.count(zero) == 0)
{
result.insert(zero);
res.push_back(zero);
}
}
}
}
return res;
}
};这里对nums进行排序，然后使用了set进行对结果去重，不出意外运行结果超时。
315 / 318 test cases passed.
Status: Time Limit Exceeded
Submitted: 4 minutes ago这里参考2sum，使用的一种高效解法是，首先排序vector nums（方便去除重复结果），然后使用两个指针，一个从前往后，另一个从后往前，然后当三者加起来等于0时加入结果，由于nums已经排序了，所以重复元素时相邻的，可以进行过滤，这样结果里就不会出现重复元素：
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> res;
sort(nums.begin(),nums.end());
int n = nums.size();
for(int i = 0;i < n - 2;i++)
{
//第一个元素如果 > 0,则后面没有3Sum == 0
if(nums[i] > 0)
break;
int second = i + 1;
int third = n - 1;
while(second < third)
{
if(nums[i] + nums[second] + nums[third] < 0)
second++;
else if (nums[i] + nums[second] + nums[third] > 0)
third--;
else
{
vector<int> result{nums[i],nums[second],nums[third]};
res.push_back(result);
//去掉重复元素
while(second < third && nums[second] == result[1]) second++;
while(second < third && nums[third] == result[2]) third--;
}
}
while(i + 1 < n && nums[i] == nums[i + 1]) i++;
}
return res;
}
};运行结果：
Runtime: 92 ms, faster than 70.79% of C++ online submissions for 3Sum.
Memory Usage: 21.6 MB, less than 5.24% of C++ online submissions for 3Sum.