题目地址(18. 四数之和)

https://leetcode-cn.com/problems/4sum/

题目描述

  1. 给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：
  3. 0 <= a, b, c, d < n
  4. a、b、c 和 d 互不相同
  5. nums[a] + nums[b] + nums[c] + nums[d] == target
  7. 你可以按 任意顺序 返回答案 。
  11. 示例 1：
  13. 输入：nums = [1,0,-1,0,-2,2], target = 0
  14. 输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
  17. 示例 2：
  19. 输入：nums = [2,2,2,2,2], target = 8
  20. 输出：[[2,2,2,2]]
  25. 提示：
  27. 1 <= nums.length <= 200
  28. -109 <= nums[i] <= 109
  29. -109 <= target <= 109

前置知识


公司

  • 暂无

思路

image.png
四数之和，和15.三数之和 (opens new window)是一个思路，都是使用双指针法, 基本解法就是在15.三数之和 (opens new window)的基础上再套一层for循环。
四数之和的双指针解法是两层for循环nums[k] + nums[i]为确定值，依然是循环内有left和right下表作为双指针，找出nums[k] + nums[i] + nums[left] + nums[right] == target的情况，三数之和的时间复杂度是O(n^2)，四数之和的时间复杂度是O(n^3) 。
那么一样的道理，五数之和、六数之和等等都采用这种解法。
对于15.三数之和 (opens new window)双指针法就是将原本暴力O(n^3)的解法，降为O(n^2)的解法，四数之和的双指针解法就是将原本暴力O(n^4)的解法，降为O(n^3)的解法。

关键点

代码

  • 语言支持：Java

Java Code:

  2. class Solution {
  3.         public List<List<Integer>> fourSum(int[] nums, int target) {
  4.             ArrayList<List<Integer>> result = new ArrayList<>();
  5.             Arrays.sort(nums);
  6.             for (int i = 0; i < nums.length; i++) {
  7.                 if (i > 0 && nums[i] == nums[i - 1]) {
  8.                     continue;
  9.                 }
  10.                 for (int j = i+1; j <nums.length ; j++) {
  11.                     if (j > i+1 && nums[j] == nums[j - 1]) {
  12.                         continue;
  13.                     }
  14.                     int left = j+1;
  15.                     int right = nums.length-1;
  16.                     while (left < right) {
  17.                         int sum = nums[i] + nums[j] + nums[left] + nums[right];
  18.                         if (sum > target) {
  19.                             right--;
  20.                         } else if (sum < target) {
  21.                             left++;
  22.                         }else {
  23.                             result.add(Arrays.asList(nums[i] , nums[j] , nums[left] , nums[right]));
  24.                             while (left < right && nums[left] == nums[left + 1]) {
  25.                                 left++;
  26.                             }
  27.                             while (left < right && nums[right] == nums[right - 1]) {
  28.                                 right--;
  29.                             }
  30.                             left++;
  31.                             right--;
  32.                         }
  33.                     }
  34.                 }
  35.             }
  36.             return result;
  37.         }
  38.     }

复杂度分析

令 n 为数组长度。

  • 时间复杂度：18. 四数之和(2) - 图2#card=math&code=O%28n%5E3%29&id=M6dw2)
  • 空间复杂度：18. 四数之和(2) - 图3#card=math&code=O%28n%29&id=DNBLl)