LeetCode 15 三数之和
🟡 中等 https://leetcode.cn/problems/3sum/description/
首先枚举i, 那就变成了两数之和的问题 [1-167两数之和Ⅱ](LeetCode 167 两数之和 II.md) , 这就要求排序; 这里要去重, 比如 -1 -1 0 1 , 这里的两个-1 只能要一个.
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
sort(nums.begin(),nums.end());
vector<vector<int>> res;
int last = INT_MAX;
for(int i = 0;i<=nums.size()-3;i++){
if(nums[i]==last) continue;
last = nums[i];
int target = -nums[i];
int j = i+1;
int k = nums.size()-1;
while(j<k){
int sum = nums[j]+nums[k];
if(sum == target){
res.push_back({nums[i],nums[j],nums[k]});
//滑动j k 防止j k 重复
while(j<k&&nums[j]==nums[j+1]) j++;
j++;
while(j<k&&nums[k]==nums[k-1]) k--;
k--;
}
if(sum>target){
k--;
}
if(sum<target){
j++;
}
}
}
return res;
}
};