题目

四数之和 - 图1

解题思路

最朴素的方法是使用四重循环枚举所有的四元组，然后使用哈希表进行去重操作，得到不包含重复四元组的最终答案。

但是这种方法的复杂度太高，需要优化。

为了避免枚举到重复四元组，则需要保证每一重循环枚举到的元素不小于其上一重循环枚举到的元素，且在同一重循环中不能多次枚举到相同的元素。所以，对数组进行排序，并且在循环过程中遵循以下两点：

  • 每一种循环枚举到的下标必须大于上一重循环枚举到的下标；
  • 同一重循环中，如果当前元素与上一个元素相同，则跳过当前元素。

上述方法可以避免枚举到重复四元组，但是由于仍使用四重循环，时间复杂度仍是O(n^4)，由于数组已经被排序，因此可以使用双指针的方法去掉一重循环。

使用两重循环分别枚举前两个数，然后在两重循环枚举到的数之后使用双指针枚举剩下的两个数。假设两重循环枚举到的前两个数分别位于下标 i 和 j，其中 i<j。初始时，左右指针分别指向下标 j+1和下标 n-1。每次计算四个数的和，并进行如下操作：

  • 如果和等于 target，则将枚举到的四个数加到答案中，然后将左指针右移直到遇到不同的数，将右指针左移直到遇到不同的数；
  • 如果和小于 target，则将左指针右移一位；
  • 如果和大于 target，则将右指针左移一位。

使用双指针枚举剩下的两个数的时间复杂度是O(n)，因此总时间复杂度是O(n4)

具体实现时，还可以进行一些剪枝操作：

  • 在确定第一个数之后，如果 nums[i]+nums[i+1]+nums[i+2]+nums[i+3]>target说明此时剩下的三个数无论取什么值，四数之和一定大于target，因此退出第一重循环；
  • 在确定第一个数之后，如果 nums[i]+nums[n-3]+nums[n-2]+nums[n-1]<target，说明此时剩下的三个数无论取什么值，四数之和一定小于target，因此第一重循环直接进入下一轮，枚举 nums[i+1]；
  • 在确定前两个数之后，如果 nums[i]+nums[j]+nums[j+1]+nums[j+2]>target，说明此时剩下的两个数无论取什么值，四数之和一定大于 target，因此退出第二重循环；
  • 在确定前两个数之后，如果 nums[i]+nums[j]+nums[n−2]+nums[n−1]<target，说明此时剩下的两个数无论取什么值，四数之和一定小于 target，因此第二重循环直接进入下一轮，枚举 nums[j+1]。

代码

  1. public static List<List<Integer>> fourSum(int[] nums, int target) {
  2.       /*定义一个返回值*/
  3.       List<List<Integer>> result=new ArrayList<>();
  4.       /*当数组为null或元素小于4个时，直接返回*/
  5.       if(nums==null||nums.length<4){
  6.           return result;
  7.       }
  8.       /*对数组进行从小到大排序*/
  9.       Arrays.sort(nums);
  10.       /*数组长度*/
  11.       int length=nums.length;
  12.       /*定义4个指针k，i，j，h  k从0开始遍历，i从k+1开始遍历，留下j和h，j指向i+1，h指向数组最大值*/
  13.       for(int k=0;k<length-3;k++){
  14.           /*当k的值与前面的值相等时忽略*/
  15.           if(k>0&&nums[k]==nums[k-1]){
  16.               continue;
  17.           }
  18.           /*获取当前最小值，如果最小值比目标值大，说明后面越来越大的值根本没戏*/
  19.           int min1=nums[k]+nums[k+1]+nums[k+2]+nums[k+3];
  20.           if(min1>target){
  21.               break;
  22.           }
  23.           /*获取当前最大值，如果最大值比目标值小，说明后面越来越小的值根本没戏，忽略*/
  24.           int max1=nums[k]+nums[length-1]+nums[length-2]+nums[length-3];
  25.           if(max1<target){
  26.               continue;
  27.           }
  28.           /*第二层循环i，初始值指向k+1*/
  29.           for(int i=k+1;i<length-2;i++){
  30.               /*当i的值与前面的值相等时忽略*/
  31.               if(i>k+1&&nums[i]==nums[i-1]){
  32.                   continue;
  33.               }
  34.               /*定义指针j指向i+1*/
  35.               int j=i+1;
  36.               /*定义指针h指向数组末尾*/
  37.               int h=length-1;
  38.               /*获取当前最小值，如果最小值比目标值大，说明后面越来越大的值根本没戏*/
  39.               int min=nums[k]+nums[i]+nums[j]+nums[j+1];
  40.               if(min>target){
  41.                   break;
  42.               }
  43.               /*获取当前最大值，如果最大值比目标值小，说明后面越来越小的值根本没戏，忽略*/
  44.               int max=nums[k]+nums[i]+nums[h]+nums[h-1];
  45.               if(max<target){
  46.                   continue;
  47.               }
  48.               /*开始j指针和h指针的表演，计算当前和，如果等于目标值，j++并去重，h--并去重，当当前和大于目标值时h--，当当前和小于目标值时j++*/
  49.               while (j<h){
  50.                   int curr=nums[k]+nums[i]+nums[j]+nums[h];
  51.                   if(curr==target){
  52.                       result.add(Arrays.asList(nums[k],nums[i],nums[j],nums[h]));
  53.                       j++;
  54.                       while(j<h&&nums[j]==nums[j-1]){
  55.                           j++;
  56.                       }
  57.                       h--;
  58.                       while(j<h&&i<h&&nums[h]==nums[h+1]){
  59.                           h--;
  60.                       }
  61.                   }else if(curr>target){
  62.                       h--;
  63.                   }else {
  64.                       j++;
  65.                   }
  66.               }
  67.           }
  68.       }
  69.       return result;
  70.   }