【leetcode】18. 四数之和

算法汇总题目题目字眼代码

1.两个for循环+双指针

思路代码时间和空间复杂度 2.解题方法，如暴力法

思路代码时间和空间复杂度

以下是所有算法汇总，包括GitHub源码地址链接：力扣算法练习汇总（持续更新…）

18. 四数之和

1、不可重复

四数之和，和15.三数之和 (opens new window) 是一个思路，都是使用双指针法, 基本解法就是在15.三数之和 (opens new window)的基础上再套一层for循环。

但是有一些细节需要注意，例如： 不要判断nums[k] > target 就返回了，三数之和 可以通过 nums[i] > 0 就返回了，因为 0 已经是确定的数了，四数之和这道题目 target是任意值。（大家亲自写代码就能感受出来）

15.三数之和 (opens new window)的双指针解法是一层for循环num[i]为确定值，然后循环内有left和right下标作为双指针，找到nums[i] + nums[left] + nums[right] == 0。

四数之和的双指针解法是两层for循环nums[k] + nums[i]为确定值，依然是循环内有left和right下标作为双指针，找出nums[k] + nums[i] + nums[left] + nums[right] == target的情况，三数之和的时间复杂度是 O ( n 2 ) O(n^2) O(n2)，四数之和的时间复杂度是 O ( n 3 ) O(n^3) O(n3) 。

那么一样的道理，五数之和、六数之和等等都采用这种解法。

对于15.三数之和 (opens new window)双指针法就是将原本暴力 O ( n 3 ) O(n^3) O(n3)的解法，降为 O ( n 2 ) O(n^2) O(n2)的解法，四数之和的双指针解法就是将原本暴力 O ( n 4 ) O(n^4) O(n4)的解法，降为 O ( n 3 ) O(n^3) O(n3)的解法。

class Solution {
    public List> fourSum(int[] nums, int target) {
       List> resultList = new ArrayList<>();
       if(nums == null || nums.length < 4){
           return resultList;
       }
       // 排序
       Arrays.sort(nums);

       for(int i = 0; i < nums.length; i++){
           if(i > 0 && nums[i - 1] == nums[i]){
               continue;
           }
           for(int j = i + 1; j < nums.length; j++){
               // 去重
               if(j > i +1 && nums[j - 1] == nums[j]){
                   continue;
               }
               int value = target - nums[i] - nums[j];
               int leftIndex = j + 1;
               int rightIndex = nums.length - 1;
               // 去重
               while(leftIndex < rightIndex){
                   if(nums[leftIndex] + nums[rightIndex] == value){
                       ArrayList list = new ArrayList<>();
                       list.add(nums[i]);
                       list.add(nums[j]);
                       list.add(nums[leftIndex]);
                       list.add(nums[rightIndex]);
                       resultList.add(list);
                       // 去重
                       while(leftIndex < rightIndex && nums[leftIndex] == nums[leftIndex+1]){
                           leftIndex++;
                       }
                       while(leftIndex < rightIndex && nums[rightIndex] == nums[rightIndex-1]){
                           rightIndex--;
                       }
                       rightIndex--;
                       leftIndex++;
                   }else if(nums[leftIndex] + nums[rightIndex] > value){
                       rightIndex--;
                   }else if(nums[leftIndex] + nums[rightIndex] < value){
                       leftIndex++;
                   }
               }
           }
       }
       return resultList;
    }
}

时间复杂度是 O ( n 3 ) O(n^3) O(n3)