题解 | #三数之和#
三数之和
https://www.nowcoder.com/practice/345e2ed5f81d4017bbb8cc6055b0b711
class Solution {
public:
vector<vector<int> > threeSum(vector<int> &num) {
vector< vector<int> > res;
int n = num.size(); //数组元素个数
if(n < 3)
return res; //特判，元素不够3个的情况
sort(num.begin(), num.end()); //先对数组元素进行排序
for(int i = 0; i < n-2; i++){ //每轮将第0个到倒数第三个元素作为三元组的第一个元素
if(i != 0 && num[i] == num[i-1]) //后两个元素相同时，无效
continue; //i+1继续验证
int left = i+1, right = n-1; //三元组首元素有效时，从其后面元素中找到左右边界
int target = -num[i]; //用首元素的相反数来验证后两个数是否存在
while(left < right){
if(num[left] + num[right] == target){ //左右两数和为目标值时
res.push_back({num[i],num[left],num[right]}); //加入返回数组中
while(left + 1 < right && num[left] == num[left+1])
left++; //左边有重复的数就跳过，
while(right - 1 > left && num[right] == num[right-1])
right--; //右边有重复的数就跳过
right--, left++; //更新左右边界，继续寻找下一对符合要求的元素
}
else if(num[left] + num[right] > target)
right--; //左右两值和更大时，右边界往左缩
else //左右两数和更小时，左边界往右移
left++;
}
}
return res;
}
};
