原题地址(中等)
方法1—排序+双指针
这题回溯递归可以做,但是超时了,而且要用set去重,会很浪费空间和时间。
而四重循环也可以做,但是也会超时,所以需要优化四重循环做法。
四重循环 = 二重循环+双指针
那怎么保证没有重复的呢?
首先先将数组排序,然后可以用set存储,最后返回的时候再赋给vector。
不过我们也可以稍作分析,直接用vector存储。
什么时候会出现重复呢? [-1, -1, 0, 1, 1]
两个-1会使得结果出现重复; [-2, -1, 0, 3, 3]
两个3也会使得结果出现重复。
也就是说当我们遍历到已经遍历过的元素时,直接跳过它就好了
具体见代码。
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
if(nums.size() < 4) return {};
vector<vector<int>> vv;
sort(nums.begin(), nums.end());
for(int i = 0; i < nums.size() -3; i++) {
if(i > 0 && nums[i] == nums[i-1]) continue; // 避免重复
for(int j = i + 1; j < nums.size() - 2; j++) {
if(j > i + 1 && nums[j] == nums[j-1]) continue; // 避免重复
int tar = target - nums[i] - nums[j];
int p = j + 1, q = nums.size() - 1;
while(p < q) {
if(nums[p] + nums[q] == tar) {
vv.push_back({nums[i], nums[j], nums[p], nums[q]});
// 两个while避免重复
while(p < q && nums[p] == nums[p+1])
p++;
while(q < q && nums[q] == nums[q-1])
q--;
p++; q--;
}
else if(nums[p] + nums[q] > tar)
q--;
else
p++;
}
}
}
return vv;
}
};