原题地址(中等)

方法1—排序+双指针

这题回溯递归可以做,但是超时了,而且要用set去重,会很浪费空间和时间。
而四重循环也可以做,但是也会超时,所以需要优化四重循环做法。

四重循环 = 二重循环+双指针

那怎么保证没有重复的呢?
首先先将数组排序,然后可以用set存储,最后返回的时候再赋给vector。
不过我们也可以稍作分析,直接用vector存储。
什么时候会出现重复呢? [-1, -1, 0, 1, 1] 两个-1会使得结果出现重复; [-2, -1, 0, 3, 3] 两个3也会使得结果出现重复。

也就是说当我们遍历到已经遍历过的元素时,直接跳过它就好了

具体见代码。

  1. class Solution {
  2. public:
  3. vector<vector<int>> fourSum(vector<int>& nums, int target) {
  4. if(nums.size() < 4) return {};
  5. vector<vector<int>> vv;
  6. sort(nums.begin(), nums.end());
  7. for(int i = 0; i < nums.size() -3; i++) {
  8. if(i > 0 && nums[i] == nums[i-1]) continue; // 避免重复
  9. for(int j = i + 1; j < nums.size() - 2; j++) {
  10. if(j > i + 1 && nums[j] == nums[j-1]) continue; // 避免重复
  11. int tar = target - nums[i] - nums[j];
  12. int p = j + 1, q = nums.size() - 1;
  13. while(p < q) {
  14. if(nums[p] + nums[q] == tar) {
  15. vv.push_back({nums[i], nums[j], nums[p], nums[q]});
  16. // 两个while避免重复
  17. while(p < q && nums[p] == nums[p+1])
  18. p++;
  19. while(q < q && nums[q] == nums[q-1])
  20. q--;
  21. p++; q--;
  22. }
  23. else if(nums[p] + nums[q] > tar)
  24. q--;
  25. else
  26. p++;
  27. }
  28. }
  29. }
  30. return vv;
  31. }
  32. };