跳到主要内容

三数之和

问题​

给你一个整数数组 nums，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i ≠ j、i ≠ k 且 j ≠ k，同时还满足 nums[i] + nums[j] + nums[k] == 0。返回所有和为 0 且不重复的三元组。

示例：

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

输入：nums = [0,1,1]
输出：[]

输入：nums = [0,0,0]
输出：[[0,0,0]]

来源：LeetCode 15. 三数之和

答案​

方法一：排序 + 双指针（推荐）​

核心思路：

  1. 先排序
  2. 固定一个数 nums[i]，用双指针在 i+1 到末尾的范围内寻找另外两个数
  3. 注意跳过重复元素以避免重复三元组
threeSum.ts
function threeSum(nums: number[]): number[][] {
  const result: number[][] = [];
  const n = nums.length;

  // 排序：O(n log n)
  nums.sort((a, b) => a - b);

  for (let i = 0; i < n - 2; i++) {
    // 剪枝：最小的数大于 0，不可能三数之和为 0
    if (nums[i] > 0) break;

    // 跳过重复的第一个数
    if (i > 0 && nums[i] === nums[i - 1]) continue;

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

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

      if (sum === 0) {
        result.push([nums[i], 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 < 0) {
        left++;   // 和太小，左指针右移
      } else {
        right--;  // 和太大，右指针左移
      }
    }
  }

  return result;
}

图解过程：

nums = [-1, 0, 1, 2, -1, -4]
排序后: [-4, -1, -1, 0, 1, 2]

i=0: nums[i]=-4
  left=1(-1), right=5(2): sum=-4-1+2=-3 < 0 → left++
  left=2(-1), right=5(2): sum=-4-1+2=-3 < 0 → left++
  left=3(0), right=5(2): sum=-4+0+2=-2 < 0 → left++
  left=4(1), right=5(2): sum=-4+1+2=-1 < 0 → left++
  left=5, left >= right → 结束

i=1: nums[i]=-1
  left=2(-1), right=5(2): sum=-1-1+2=0 ✓ → 记录 [-1,-1,2]
    跳过重复：left=3, right=4
  left=3(0), right=4(1): sum=-1+0+1=0 ✓ → 记录 [-1,0,1]
    left=4, right=3 → 结束

i=2: nums[i]=-1, 和 nums[1] 相同 → 跳过

i=3: nums[i]=0 > 0 → break

结果：[[-1,-1,2], [-1,0,1]]
复杂度分析
  • 时间复杂度：O(n2)O(n^2) — 排序 O(nlog⁡n)O(n\log n) + 双重循环 O(n2)O(n^2)
  • 空间复杂度：O(log⁡n)O(\log n) — 排序的栈空间（不算输出）
去重是关键

去重有三个位置，缺一不可：

  1. i > 0 && nums[i] === nums[i-1] → 跳过相同的第一个数
  2. nums[left] === nums[left+1] → 找到答案后跳过相同的第二个数
  3. nums[right] === nums[right-1] → 找到答案后跳过相同的第三个数

方法二：哈希表​

固定两个数，用哈希表查找第三个数：

threeSumHash.ts
function threeSum(nums: number[]): number[][] {
  const result: number[][] = [];
  const n = nums.length;
  nums.sort((a, b) => a - b);

  for (let i = 0; i < n - 2; i++) {
    if (i > 0 && nums[i] === nums[i - 1]) continue;

    const seen = new Set<number>();
    for (let j = i + 1; j < n; j++) {
      const complement = -(nums[i] + nums[j]);

      if (seen.has(complement)) {
        result.push([nums[i], complement, nums[j]]);
        // 跳过重复
        while (j + 1 < n && nums[j] === nums[j + 1]) j++;
      }

      seen.add(nums[j]);
    }
  }

  return result;
}
对比
  • 哈希表方法时间复杂度也是 O(n2)O(n^2)，但空间复杂度 O(n)O(n)
  • 双指针方法不需要额外空间（原地排序），面试中更受青睐

常见面试追问​

Q1: 两数之和与三数之和的关系？​

答案：三数之和本质上是"固定一个数，在剩余数组中找两数之和"。两数之和的目标值变成了 -nums[i]。

  • 两数之和用哈希表 O(n)O(n)
  • 三数之和外层固定一个数 O(n)O(n)，内层双指针 O(n)O(n)，总计 O(n2)O(n^2)

Q2: 四数之和怎么做？(LeetCode 18)​

答案：再套一层循环，固定两个数后用双指针：

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

  for (let i = 0; i < n - 3; i++) {
    if (i > 0 && nums[i] === nums[i - 1]) continue;

    for (let j = i + 1; j < n - 2; j++) {
      if (j > i + 1 && nums[j] === nums[j - 1]) continue;

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

      while (left < right) {
        const sum = nums[i] + nums[j] + nums[left] + nums[right];
        if (sum === target) {
          result.push([nums[i], nums[j], 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 result;
}
// 时间复杂度：O(n³)

Q3: 最接近的三数之和？(LeetCode 16)​

答案：

function threeSumClosest(nums: number[], target: number): number {
  nums.sort((a, b) => a - b);
  let closest = nums[0] + nums[1] + nums[2];

  for (let i = 0; i < nums.length - 2; i++) {
    let left = i + 1;
    let right = nums.length - 1;

    while (left < right) {
      const sum = nums[i] + nums[left] + nums[right];
      if (Math.abs(sum - target) < Math.abs(closest - target)) {
        closest = sum;
      }
      if (sum < target) left++;
      else if (sum > target) right--;
      else return target; // 完全匹配
    }
  }

  return closest;
}

相关链接​