四数之和

题目描述

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

示例 2：

示例 3：

约束条件

• 1 <= nums.length <= 200
• -10^9 <= nums[i] <= 10^9
• -10^9 <= target <= 10^9

解题思路

算法思路

这道题是「15. 三数之和」的延伸，核心思路是：排序 + 双指针 + 剪枝优化。

1. 排序数组：将数组从小到大排序，方便后续去重和双指针操作
2. 固定两个数：使用两层循环固定前两个数 nums[i] 和 nums[j]
3. 双指针查找：对剩余部分使用双指针 l 和 r 查找满足条件的另外两个数
4. 去重处理：
   • 第一层循环：如果 nums[i] === nums[i-1]，跳过避免重复
   • 第二层循环：如果 nums[j] === nums[j-1]，跳过避免重复
   • 找到结果后：移动指针时跳过相同元素
5. 剪枝优化：利用排序特性提前终止无效循环

剪枝优化详解

// 剪枝1：当前最小的四个数之和都大于target，后面不可能有解
if (nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) break;

// 剪枝2：当前数与最大的三个数之和都小于target，当前数太小，尝试下一个
if (nums[i] + nums[n - 1] + nums[n - 2] + nums[n - 3] < target) continue;

这两个剪枝在数据量大时能显著提升性能。

代码实现

方法一：基础双指针法

function fourSum(nums: number[], target: number): number[][] {
  nums.sort((a, b) => a - b);
  let res = [];

  for (let i = 0; i < nums.length - 3; i++) {
    // 去重：跳过重复的第一个数
    if (i > 0 && nums[i] === nums[i - 1]) continue;

    for (let j = i + 1; j < nums.length - 2; j++) {
      // 去重：跳过重复的第二个数
      if (j > i + 1 && nums[j] === nums[j - 1]) continue;

      let l = j + 1;
      let r = nums.length - 1;

      while (l < r) {
        const sum = nums[i] + nums[j] + nums[l] + nums[r];

        if (sum > target) {
          r--; // 和太大，右指针左移
        } else if (sum < target) {
          l++; // 和太小，左指针右移
        } else {
          // 找到一组解
          res.push([nums[i], nums[j], nums[l], nums[r]]);

          // 去重：跳过重复的第三个数
          while (l < r && nums[l] === nums[l + 1]) l++;
          // 去重：跳过重复的第四个数
          while (l < r && nums[r] === nums[r - 1]) r--;

          l++;
          r--;
        }
      }
    }
  }

  return res;
}

方法二：剪枝优化版（推荐）

在基础版本上增加剪枝，提升性能：

function fourSum(nums: number[], target: number): number[][] {
  nums.sort((a, b) => a - b);
  const n = nums.length;
  const res: number[][] = [];

  for (let i = 0; i < n - 3; i++) {
    // 去重：跳过重复的第一个数
    if (i > 0 && nums[i] === nums[i - 1]) continue;

    // 剪枝1：当前最小四数之和大于target，后续不可能有解
    if (nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) break;

    // 剪枝2：当前数与最大三数之和小于target，当前数太小
    if (nums[i] + nums[n - 1] + nums[n - 2] + nums[n - 3] < target) continue;

    for (let j = i + 1; j < n - 2; j++) {
      // 去重：跳过重复的第二个数
      if (j > i + 1 && nums[j] === nums[j - 1]) continue;

      // 剪枝3：当前最小四数之和大于target
      if (nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target) break;

      // 剪枝4：当前两数与最大两数之和小于target
      if (nums[i] + nums[j] + nums[n - 1] + nums[n - 2] < target) continue;

      let l = j + 1;
      let r = n - 1;

      while (l < r) {
        const sum = nums[i] + nums[j] + nums[l] + nums[r];

        if (sum > target) {
          r--; // 和太大，右指针左移
        } else if (sum < target) {
          l++; // 和太小，左指针右移
        } else {
          // 找到一组解
          res.push([nums[i], nums[j], nums[l], nums[r]]);

          // 去重：跳过重复的第三个数
          while (l < r && nums[l] === nums[l + 1]) l++;
          // 去重：跳过重复的第四个数
          while (l < r && nums[r] === nums[r - 1]) r--;

          l++;
          r--;
        }
      }
    }
  }

  return res;
}

算法步骤

1. 排序：nums.sort((a, b) => a - b) - O(n log n)
2. 第一层循环：固定第一个数 nums[i]，范围 [0, n-4]
   • 去重检查
   • 剪枝检查
3. 第二层循环：固定第二个数 nums[j]，范围 [i+1, n-3]
   • 去重检查
   • 剪枝检查
4. 双指针扫描：l 从 j+1 开始，r 从 n-1 开始
   • sum > target：r--
   • sum < target：l++
   • sum === target：记录结果，去重后继续
5. 返回结果：所有不重复的四元组

关键点总结

1. 排序是基础：所有去重和剪枝都依赖排序后的数组特性
2. 去重的三个层次：
   • 第一个数去重：i > 0 && nums[i] === nums[i-1]
   • 第二个数去重：j > i+1 && nums[j] === nums[j-1]
   • 双指针去重：找到解后跳过相同元素
3. 剪枝的四个优化：
   • 最小四数和大于 target → break
   • 当前数+最大三数和小于 target → continue
   • 当前两数+最小两数和大于 target → break
   • 当前两数+最大两数和小于 target → continue
4. 注意溢出：题目范围 -10^9 ~ 10^9，四数之和可能溢出 32 位整数，TypeScript 中数字类型足够处理