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;
}
};``````

``````315 / 318 test cases passed.
Status: Time Limit Exceeded
Submitted: 4 minutes ago``````

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