三数之和与四数之和 18

发布时间 2024-01-13 16:38:07作者: 云撤~


首先做的时候降重不好处理。看了卡哥的视频后知道几个关键点:(以四数之和为例)
1 最开始确定的两个数,要降重的话,必须当前数与上一个数不同,即nums[i]!=nums[i-1}。
之所以这样,而不是i+1,是因为是先要包含符合条件的案例,然后再排除。+的话就直接排除了。
2 left和right,也要降重,这个如果相同的话就直接往后遍历就行,全部过滤掉。
综上所述,先找可能会重复的地方,也就是多少个点,然后想然后降重。

点击查看代码
class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
sort(nums.begin(),nums.end());
vector<int>v;
vector<vector<int>>cnt;
for(int i=0;i<nums.size();i++){
    if(nums[i]>target&&target>=0){break;}
    if(i>0&&nums[i]==nums[i-1]){continue;}
    for(int j=i+1;j<nums.size();j++){
        if(nums[i]+nums[j]>target&&target>=0){break;}
        if(j>i+1&&nums[j]==nums[j-1]){continue;}
      
        int left=j+1;int right=nums.size()-1;
        while(left<right){
            if((long)nums[i]+nums[j]+nums[left]+nums[right]>target){
                --right;
            }
            else if((long)nums[i]+nums[j]+nums[left]+nums[right]<target){
                ++left;
            }
            else{
                v.push_back(nums[i]);
                v.push_back(nums[j]);
                v.push_back(nums[left]);
                v.push_back(nums[right]);
                cnt.push_back(v);
                while(left<right&&nums[left]==nums[left+1]){++left;}
                while(right>left&&nums[right]==nums[right-1]){--right;}
                ++left;
                --right;
                v.clear();
            }
        }

        
}
    }
    return cnt;
    }
};