三数之和说是,双指针,不过有点灵活(对我来说)
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> qq;
if(nums.size()<3)return qq;//小于3一定没有
sort(nums.begin(),nums.end());
int l,r,sum;
for(int i=0;i<nums.size();i++)
{
if(nums[i]>0)return qq;//从前往后找,当当前元素大于零,后面不得重复所以不可能有解
//直接返回
if(i&&nums[i]==nums[i-1])continue;//去除重复元素
l=i+1,r=nums.size()-1;//双指针,一个指向i往后一个元素,一个指向尾部
//两个指针不断在后面找数与当前数取和
while(l<r)
{
sum=nums[i]+nums[l]+nums[r];//三数之和
if(sum<0)l++;//当三数之和小于零向右寻找更大的数,否则相反
if(sum>0)r--;
else if(sum==0){
vector<int> q={nums[i],nums[l],nums[r]};
qq.push_back(q);
while(l<r&&nums[l]==nums[l+1])l++;//去重
while(l<r&&nums[r]==nums[r-1])r--;//去除重复
l++,r--;//总得移动指针,不然其他条件不满足不移动,死循环
}
}
}
return qq;
}
};