18. 四数之和 Medium

给你一个由 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]]

解题思路

输入：一个整数数组 nums，一个整数 target

输出：找出所有不重复的四元组 [a, b, c, d]，满足 a + b + c + d == target

本题是典型的 排序 + 相向双指针 问题。

这道题解法和三数之和类似，我们可以先对数组进行排序，然后固定两个数 nums[a] nums[a+1]，接着在 a+2 ~ n-1 范围内使用双指针

本质上就是固定两个数 nums[a], nums[b] 之后再去找另外两个值使得四个数之和为 target

代码实现

python

from typing import List

class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        nums.sort()  # 先排序，方便去重和使用双指针
        n = len(nums)
        res = []

        for a in range(n - 3):
            # 跳过重复元素
            if a > 0 and nums[a] == nums[a - 1]:
                continue

            # 剪枝：最小四数之和都大于 target，后面不用继续了
            if nums[a] + nums[a + 1] + nums[a + 2] + nums[a + 3] > target:
                break

            # 剪枝：当前固定数加上最大三个数之和都小于 target，跳过当前
            if nums[a] + nums[n - 1] + nums[n - 2] + nums[n - 3] < target:
                continue

            for b in range(a + 1, n - 2):
                # 跳过重复元素
                if b > a + 1 and nums[b] == nums[b - 1]:
                    continue

                # 剪枝：当前 a, b 固定，后两个最小数都加起来大于 target，后面不用继续了
                if nums[a] + nums[b] + nums[b + 1] + nums[b + 2] > target:
                    break

                # 剪枝：当前 a, b 固定，后两个最大数都加起来还小于 target，继续下一轮
                if nums[a] + nums[b] + nums[n - 1] + nums[n - 2] < target:
                    continue

                # 双指针寻找另外两个数
                left, right = b + 1, n - 1
                while left < right:
                    total = nums[a] + nums[b] + nums[left] + nums[right]
                    
                    if total == target:
                        res.append([nums[a], nums[b], nums[left], nums[right]])
                        left += 1
                        right -= 1

                        # 跳过重复元素
                        while left < right and nums[left] == nums[left - 1]:
                            left += 1
                        while left < right and nums[right] == nums[right + 1]:
                            right -= 1

                    elif total < target:
                        left += 1
                    else:
                        right -= 1

        return res

javascript

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[][]}
 */
var fourSum = function(nums, target) {
    nums.sort((a, b) => a - b); // 先对数组排序，方便后续去重和双指针操作
    const res = [];
    const n = nums.length;

    for (let a = 0; a < n - 3; a++) {
        // 跳过重复元素，避免结果重复
        if (a > 0 && nums[a] === nums[a - 1]) continue;

        // 剪枝：最小可能值已经大于目标，后续不可能再满足条件
        if (nums[a] + nums[a + 1] + nums[a + 2] + nums[a + 3] > target) break;

        // 剪枝：当前值加上最大三个数仍小于目标，跳过当前
        if (nums[a] + nums[n - 1] + nums[n - 2] + nums[n - 3] < target) continue;

        for (let b = a + 1; b < n - 2; b++) {
            // 跳过重复元素
            if (b > a + 1 && nums[b] === nums[b - 1]) continue;

            // 剪枝：当前组合下最小可能值超过目标
            if (nums[a] + nums[b] + nums[b + 1] + nums[b + 2] > target) break;

            // 剪枝：当前组合下最大可能值仍小于目标
            if (nums[a] + nums[b] + nums[n - 1] + nums[n - 2] < target) continue;

            let left = b + 1;
            let right = n - 1;

            while (left < right) {
                const sum = nums[a] + nums[b] + nums[left] + nums[right];

                if (sum === target) {
                    res.push([nums[a], nums[b], nums[left], nums[right]]);

                    // 跳过重复的第3个数
                    while (left < right && nums[left] === nums[left + 1]) left++;
                    left++;

                    // 跳过重复的第4个数
                    while (left < right && nums[right] === nums[right - 1]) right--;
                    right--;

                } else if (sum < target) {
                    left++; // 总和偏小，左指针右移
                } else {
                    right--; // 总和偏大，右指针左移
                }
            }
        }
    }

    return res;
};

复杂度分析

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

空间复杂度：O(1)

链接

18 国际版

18 中文版