首先做的时候降重不好处理。看了卡哥的视频后知道几个关键点:(以四数之和为例)
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;
}
};