【LeetCode-中等题】18. 四数之和

题目

方法一：双指针（定2动2）

这题可以参考【LeetCode-中等题】15. 三数之和
区别在于，三数之和只需要用一个for循环定住一个数，然后设置两个前后指针来根据sum的值和目标值比较来滑动指针

那么这题也是同理的，我们需要做的事就是定住2个数，要用两个for循环定住两个数，然后设置两个前后指针来根据sum的值和目标值比较来滑动指针

里面的处理细节很多需要注意，提前处理一些不可能满足条件的情况，减少时间复杂度

class Solution {
//for定2 指针动2
    public List<List<Integer>> fourSum(int[] nums, int target) {
      int len =  nums.length;
      if(nums == null||len < 4 ) return new ArrayList<>();
      List<List<Integer>> res = new ArrayList<>();
      List<Integer> zres = null;
      Arrays.sort(nums);
      for(int i = 0 ;i< len-3 ;i++){
           //本身就是排序的数组  若第一个数就大于等于target了那么再加上任何一个数都会大于target，所以直接break
        //    if(nums[i]>target)  break;
        //这个条件不能要（对比LeetCode 15. 三数之和）  如果target是负数，第一个数大于target  在往下加可能会越来越小也是可以=taget的
                                     //但是如果target为0或正数，那么第一个数大于target  往下加会越来越大
          //去重操作  如果nums[i]==nums[i-1] 会得到一份与nums[i-1]一样的结果集
          if(i>0&&nums[i]==nums[i-1]) continue;
           // 若以i开头的四个元素就已经大于target了 那就无需做任何操作了，没必要了，在往后面加再怎么也会大于target
          if((long)nums[i]+nums[i+1]+nums[i+2]+nums[i+3] > target) break;
          // 若以i开头元素和数组末尾的三个元素就还小于target了 那就没必要做此次循环，毕竟i加上后面最大的三个数都比target小
          if((long)nums[i]+nums[len-1]+nums[len-2]+nums[len-3] < target) continue;
          for(int j = i+1 ;j< len-2 ;j++){//这里就和 LeetCode 15. 三数之和  一样的原理  唯一多了一个提前判断
              // 这里的三个if与上面同理  
               if(j>i+1&&nums[j]==nums[j-1]) continue;
               if((long)nums[i]+nums[j]+nums[j+1]+nums[j+2] > target) break;
               if((long)nums[i]+nums[j]+nums[len-1]+nums[len-2] < target) continue;
               int left = j+1;
               int right = len-1;
               while(left < right){
                   long sum =(long) nums[i]+nums[j]+nums[left]+nums[right];
                   if(sum == target) {
                       zres = new ArrayList<>();//满足要求的子结果集
                       zres.add(nums[i]);
                       zres.add(nums[j]);
                       zres.add(nums[left]);
                       zres.add(nums[right]);
                       res.add(zres);//加入大结果集
                       while(left < right &&nums[left]==nums[left+1]) left++;//两个指针的去重
                       while(left < right &&nums[right]==nums[right-1]) right--;
                       left++;//移动指针到不重复的新区域
                       right--;
                   }else if(sum >target)  right--;//缩小数值
                    else left++;//扩大数值
               }
          }
      }
      return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47