2026年2月2日学习记录

今日学习内容

在做 LeetCode 的 三数之和（15题） 和 四数之和（18题） 时，我发现了一个规律：

• 3Sum：固定 1 个数，双指针找另外 2 个 → O(n²)
• 4Sum：固定 2 个数，双指针找另外 2 个 → O(n³)

那如果是 5Sum、6Sum、nSum 呢？难道要写 n-2 层嵌套循环吗？

这样的代码不仅难写、难维护，还不够优雅。于是我想到了 递归 的解决方案。

---

问题分析

嵌套循环的困境

如果我们继续沿用固定 n-2 个数 + 双指针的思路：

// 3Sum: 1层循环 + 双指针
for (let i = 0; i < n; i++) {
  // 双指针
}

// 4Sum: 2层循环 + 双指针
for (let i = 0; i < n; i++) {
  for (let j = i + 1; j < n; j++) {
    // 双指针
  }
}

// 5Sum: 3层循环 + 双指针？
for (let i = 0; i < n; i++) {
  for (let j = i + 1; j < n; j++) {
    for (let k = j + 1; k < n; k++) {
      // 双指针
    }
  }
}

问题显而易见：

• 随着 n 增大，嵌套层数无限增加
• 代码重复度高，无法复用
• 可维护性极差

---

递归解法：统一处理 nSum

核心思想

观察上面的模式，我们可以发现：

1. 所有 nSum 问题最终都归结为 2Sum
2. nSum 可以转化为：固定一个数 + (n-1)Sum

这正是递归的经典应用场景！

递归结构

nSum(nums, n, start, target)
  ↓
固定 nums[i]，递归调用 (n-1)Sum(nums, n-1, i+1, target-nums[i])
  ↓
固定 nums[j]，递归调用 (n-2)Sum(nums, n-2, j+1, target-nums[j])
  ↓
...
  ↓
2Sum（递归出口，使用双指针）

---

代码实现

function nSum(nums: number[], n: number, start: number, target: number): number[][] {
  const res: number[][] = [];
  const len = nums.length;

  // ============ 递归出口：2Sum ============
  if (n === 2) {
    let left = start;
    let right = len - 1;

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

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

        // 去重：跳过相同元素
        while (left < right && nums[left] === nums[left + 1]) left++;
        while (left < right && nums[right] === nums[right - 1]) right--;

        left++;
        right--;
      } else if (sum < target) {
        left++;
      } else {
        right--;
      }
    }

    return res;
  }

  // ============ n > 2 的情况：递归 ============
  for (let i = start; i < len - n + 1; i++) {
    // 去重：跳过重复的数字
    if (i > start && nums[i] === nums[i - 1]) continue;

    // 剪枝优化（可选但推荐）
    // 如果当前数字乘以 n 都大于 target，后面不可能有解
    if (nums[i] * n > target) break;
    // 如果最大数字乘以 n 都小于 target，当前数字太小
    if (nums[len - 1] * n < target) continue;

    // 递归调用 (n-1)Sum
    const subResults = nSum(nums, n - 1, i + 1, target - nums[i]);

    // 将当前数字与子结果组合
    for (const sub of subResults) {
      res.push([nums[i], ...sub]);
    }
  }

  return res;
}

---

使用示例

3Sum（LeetCode 15）

function threeSum(nums: number[]): number[][] {
  nums.sort((a, b) => a - b);
  return nSum(nums, 3, 0, 0);
}

4Sum（LeetCode 18）

function fourSum(nums: number[], target: number): number[][] {
  nums.sort((a, b) => a - b);
  return nSum(nums, 4, 0, target);
}

5Sum、6Sum、任意 nSum

function fiveSum(nums: number[], target: number): number[][] {
  nums.sort((a, b) => a - b);
  return nSum(nums, 5, 0, target);
}

---

参数说明

参数	说明
nums	已排序的数组
n	需要找 n 个数的和
start	从数组的哪个位置开始搜索
target	目标和

关键点：

• 调用前必须先对数组排序
• start 参数确保不会重复使用同一个元素
• target 会随着递归逐层减少

---

算法分析

时间复杂度

• 2Sum：O(n)（双指针）
• 3Sum：O(n²)（1 层循环 + 2Sum）
• 4Sum：O(n³)（2 层循环 + 2Sum）
• nSum：O(n^(n-1))（(n-2) 层递归 + 2Sum）

虽然时间复杂度没有改善，但代码的可维护性大大提高。

空间复杂度

• 递归深度：O(n)（最多 n-2 层递归）
• 结果数组：不计入

总空间复杂度：O(n)

---

优化技巧

1. 去重

// 在循环中跳过重复元素
if (i > start && nums[i] === nums[i - 1]) continue;

// 在双指针中跳过重复元素
while (left < right && nums[left] === nums[left + 1]) left++;

2. 剪枝

// 当前数字太大，后面不可能有解
if (nums[i] * n > target) break;

// 当前数字太小，继续下一个
if (nums[len - 1] * n < target) continue;

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

---

总结

递归方法的优势

1. 代码复用：一个函数解决所有 nSum 问题
2. 逻辑清晰：递归结构符合问题的本质
3. 易于维护：不用写多层嵌套循环
4. 扩展性强：轻松应对任意 n 值

何时使用

• 当问题可以分解为规模更小的同类问题时
• 当嵌套循环层数不确定或非常多时
• 当需要统一处理一类问题时

注意事项

• 调用前务必先排序
• 注意去重和剪枝
• 理解递归出口（2Sum）的实现

---

这次的思考让我意识到，算法的本质往往是找到问题的递归结构。当我们能够用统一的方式处理一类问题时，代码会变得更加优雅和强大。