双指针
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> res;
int n = nums.size();
if (n < 3) return res;
sort(nums.begin(), nums.end());
for (int i = 0; i < n; i ++ )
{
if (nums[i] > 0) return res; //若第一个数大于0,后边就不会等于0了
if (i > 0 && nums[i] == nums[i - 1]) continue; //跳过重复数字
int l = i + 1, r = n - 1;
while (l < r)
{
if (nums[i] + nums[l] + nums[r] == 0)
{
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 -- ; //右指针后退
}
else if (nums[i] + nums[l] + nums[r] > 0)
{
r -- ; //和大于0,要减少总和之值,即右指针后退
}
else
{
l ++ ; //和小于0,要增加总和之值,即左指针前进
}
}
}
return res;
}
};