18.四数之和

难度：中等

给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且 不重复 的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：

0 <= a, b, c, d < n
a、b、c 和 d 互不相同
nums[a] + nums[b] + nums[c] + nums[d] == target

你可以按 任意顺序 返回答案。

示例 1：

输入：nums = [1,0,-1,0,-2,2], target = 0
输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

示例 2：

输入：nums = [2,2,2,2,2], target = 8
输出：[[2,2,2,2]]

提示：

1 <= nums.length <= 200
-109 <= nums[i] <= 109
-109 <= target <= 109

解题思路

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

但是有一些细节需要注意，例如：不要因为 nums[i] > target 或者 nums[i] + nums[j] > target 就返回了。

三数之和可以通过 nums[i] > 0 就返回，因为目标值 0 已经是确定的数了，四数之和这道题目中目标值 target 是任意值。

比如：数组是 [-4, -3, -2, -1]，target 是 -10，不能因为 -4 > -10 而跳过，因为负数相加会变得更小。

但是我们仍然可以做一些剪枝操作：

最小值剪枝：如果当前遍历到的数字 nums[i] 加上剩余可能的最小三个数的和已经大于目标值 target，那么后续的数无论如何组合，总和都不可能等于 target。因此，可以直接终止循环。
最大值剪枝：如果当前遍历到的数字 nums[i] 加上剩余可能的最大三个数的和仍然小于目标值 target，那么即使增加后面的数字，总和也不可能等于 target。因此，可以跳过当前循环继续下一个数字的遍历。

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

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

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

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

我的代码

java

public List<List<Integer>> fourSum(int[] nums, int target) {
    // 双基准快排算法，对数组进行排序
    Arrays.sort(nums);
    List<List<Integer>> result = new ArrayList<>();
    for (int i = 0; i < nums.length - 3; i++) {
        // 一级剪枝,这里使用long是因为数太大，int会溢出
        // 最小值剪枝
        if ((long) nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) {
            break;
        }
        // 最大值剪枝
        if ((long) nums[i] + nums[nums.length - 1] + nums[nums.length - 2] + nums[nums.length - 3] < target) {
            continue;
        }
        // 对nums[i]去重
        if (i > 0 && nums[i] == nums[i - 1]) {
            continue;
        }
        for (int j = i + 1; j < nums.length - 2; j++) {
            // 二级剪枝
            if ((long) nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target) {
                break;
            }
            if ((long) nums[i] + nums[j] + nums[nums.length - 1] + nums[nums.length - 2] < target) {
                continue;
            }
            // 对nums[i]去重
            if (j > i + 1 && nums[j] == nums[j - 1]) {
                continue;
            }
            // 使用双指针法
            int left = j + 1;
            int right = nums.length - 1;
            while (left < right) {
                //这里使用long是因为数太大，int会溢出
                long sum = (long) nums[i] + nums[j] + nums[left] + nums[right];
                if (sum > target) {
                    right--;
                } else if (sum < target) {
                    left++;
                } else if (sum == target) {
                    result.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));
                    // 对nums[left]和nums[right]去重
                    while (left < right && nums[right - 1] == nums[right]) {
                        right--;
                    }
                    while (left < right && nums[left + 1] == nums[left]) {
                        left++;
                    }
                    // 找到答案时，双指针同时收缩
                    right--;
                    left++;
                }
            }
        }
    }
    return result;
}

时间复杂度: O(n^3)

空间复杂度: O(1)

总结

什么时候使用哈希法：

当我们需要快速查询一个元素是否出现过，或者一个元素是否在集合里的时候，就要第一时间想到哈希法。

本题，我们不仅要知道元素有没有遍历过，还要知道这个元素对应的下标，需要使用 key value 结构来存放，key 来存元素，value 来存下标，那么使用 map 正合适。

使用数组和 set 来做哈希法的局限：

数组的大小是受限制的，而且如果元素很少，而哈希值太大会造成内存空间的浪费。
set 是一个集合，里面放的元素只能是一个 key，而本题，不仅要判断 y 是否存在而且还要记录 y 的下标位置，因为要返回 x 和 y 的下标。所以 set 也不能用。

18.四数之和 ​

解题思路 ​

我的代码 ​

总结 ​

18.四数之和

解题思路

我的代码

总结