算法 - 两数之和 (Two Sum)

Posted on

1. 题目

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回它们的数组下标。

要求：

  • 每种输入只会对应一个答案（保证有且仅有一组解）。
  • 同一个元素不能使用两遍。
  • 可以按任意顺序返回答案。

示例:

1
2
3
输入: nums = [2, 7, 11, 15], target = 9
输出: [0, 1]
解释: nums[0] + nums[1] == 9，返回 [0, 1]

2. 解题思路

2.1 暴力法（不推荐）

两层循环枚举所有 (i, j) 组合，判断 nums[i] + nums[j] === target。

  • 时间复杂度：O(n²)
  • 空间复杂度：O(1)

面试时可以作为引子，但要立刻说出瓶颈在于「查找另一个数是否存在」这一步是线性的。

2.2 哈希表（最优）

核心转换：对于当前数 x，我们真正想知道的是「数组里有没有 target - x」。

遍历数组时，用 Map 记录「已经看过的数 -> 下标」。对每个 nums[i]：

  1. 计算补数 complement = target - nums[i]。
  2. 若 complement 已在 Map 中，直接返回 [map.get(complement), i]。
  3. 否则把 nums[i] -> i 存进 Map，继续。

因为「先查后存」，天然避免了同一个元素被使用两次。

  • 时间复杂度：O(n)，只需一次遍历。
  • 空间复杂度：O(n)，最坏存 n 个数。

3. TypeScript 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
function twoSum(nums: number[], target: number): number[] {
    const seen = new Map<number, number>();

    for (let i = 0; i < nums.length; i++) {
        const complement = target - nums[i];

        if (seen.has(complement)) {
            return [seen.get(complement)!, i];
        }

        seen.set(nums[i], i);
    }

    // 题目保证有解，理论上不会走到这里
    return [];
}

// 测试
console.log(twoSum([2, 7, 11, 15], 9)); // [0, 1]
console.log(twoSum([3, 2, 4], 6));      // [1, 2]
console.log(twoSum([3, 3], 6));         // [0, 1]

4. 面试延伸

  • 为什么用 Map 而不是 Object？ 数字做 key 时 Map 无需字符串化，也避免原型链上的键冲突，查找语义更清晰。
  • 如果数组已排序呢？ 可用「双指针」左右夹逼，空间降到 O(1)，这也是 [三数之和] 的基础。
  • 返回所有不重复组合？ 那就需要排序 + 去重，思路升级为 k-Sum 通用解法。

难度：简单 | LeetCode 1 题 | 高频面试开场题