Grind 75 刷题第 1 题：Two Sum，两数之和到底该怎么想？

准备美国程序员面试时，很多人都会碰到 Grind 75。

它不是让你漫无目的地刷几百道题，而是从常见面试题中挑出一组有代表性的题目，帮助你集中练习数组、哈希表、链表、二叉树、动态规划等核心知识。

今天从最经典的一道题开始：

Two Sum，两数之和。

这道题看起来很简单，但它几乎包含了算法面试最常见的一种优化思路：

如何用额外的存储空间，减少重复查找。

题目

给定一个整数数组 nums 和一个整数 target，找出数组中两个数字，使它们相加等于 target。

返回这两个数字的数组下标。

假设每组输入只有一个答案，并且同一个元素不能使用两次。

例如：

nums = [2, 7, 11, 15]
target = 9

因为：

nums[0] + nums[1] = 2 + 7 = 9

所以返回：

[0, 1]

注意，题目要求返回的是下标，不是数字本身。

第一反应：两个数字两两比较

最容易想到的方法，是用两层循环。

先拿第一个数字和后面的每个数字比较，再拿第二个数字和后面的数字比较。

def two_sum(nums, target):
for i in range(len(nums)):
for j in range(i + 1, len(nums)):
if nums[i] + nums[j] == target:
return [i, j]

这个方法可以得到正确答案，但时间复杂度是：

O(n²)

数组较小时没问题，但如果数组里有很多数字，就会进行大量重复查找。

面试官通常会继续问：

能不能只遍历一次数组？

优化思路：不要找两个数，只找当前数字缺少的那个数

假设当前遍历到数字 2，目标值是 9。

我们真正需要找的是：

9 - 2 = 7

这个 7 通常叫作 complement，也就是当前数字对应的“补数”。

计算公式是：

complement = target - nums[i]

接下来只需要判断：

这个 complement 之前有没有出现过？

如果出现过，说明已经找到了答案。

如果没有出现，就把当前数字和它的下标存入哈希表，继续遍历。

twosum.png

用一个例子走完整个流程

输入：

nums = [2, 7, 11, 15]
target = 9

开始时，哈希表为空：

map = {}

第一步：指针来到下标 0

当前数字：

nums[0] = 2

计算 complement：

complement = 9 - 2 = 7

检查 7 是否在 map 中：

不在

所以先把当前数字 2 和它的下标 0 存进 map：

map = {
2: 0
}

继续下一轮循环。

第二步：指针来到下标 1

当前数字：

nums[1] = 7

计算 complement：

complement = 9 - 7 = 2

检查 2 是否在 map 中。

此时 map 是：

{
2: 0
}

发现 2 已经存在，并且它的下标是 0。

当前数字 7 的下标是 1。

所以直接返回：

[0, 1]

程序到这里结束，不需要继续检查后面的 11 和 15。

整个过程可以简化为：

i = 0
当前数字 2
需要寻找 7
map 中没有 7
把 2 和下标 0 存入 map

↓

i = 1
当前数字 7
需要寻找 2
map 中存在 2
返回 [0, 1]

Python 解法

def two_sum(nums, target):
seen = {}

for i, num in enumerate(nums):
complement = target - num

if complement in seen:
return [seen[complement], i]

seen[num] = i

return []

这里的 seen 就是哈希表。

它保存的结构是：

数字: 下标

例如：

{
2: 0
}

表示数字 2 出现在数组下标 0 的位置。

JavaScript 解法

function twoSum(nums, target) {
const seen = new Map();

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 [];
}

JavaScript 使用 Map 保存已经遍历过的数字和下标。

核心逻辑与 Python 完全相同。

为什么要先检查，再放进 map？

这是 Two Sum 最容易被忽略的地方。

例如：

nums = [3, 2, 4]
target = 6

当指针来到第一个数字 3 时：

complement = 6 - 3 = 3

如果先把当前的 3 放进 map，再检查 complement，就可能错误地把同一个元素使用两次。

但题目规定：

同一个数组元素不能重复使用。

所以正确顺序应该是：

先检查 complement 是否在 map 中
再把当前数字放进 map

重复数字怎么办？

例如：

nums = [3, 3]
target = 6

第一轮：

当前数字 = 3
complement = 3
map 中没有 3
存入 {3: 0}

第二轮：

当前数字 = 3
complement = 3
map 中已经有 3
返回 [0, 1]

所以哈希表方法也可以正确处理重复数字。

时间复杂度

数组只需要遍历一次。

哈希表的平均查询时间是 O(1)，所以总时间复杂度是：

O(n)

因为最坏情况下需要把数组中的元素存入哈希表，所以空间复杂度是：

O(n)

与两层循环相比：

暴力解法：时间 O(n²)，空间 O(1)
哈希表：时间 O(n)，空间 O(n)

这就是典型的：

用空间换时间。

面试时怎么讲？

面试时可以先说暴力解法，再主动提出优化。

可以这样表达：

最直接的方法是使用两层循环，检查数组中的每一对数字，时间复杂度是 O(n²)。
为了减少重复查找，我可以使用哈希表保存已经遍历过的数字及其下标。遍历当前数字时，计算 target 减去当前数字得到 complement。如果 complement 已经在哈希表中，就返回 complement 的下标和当前下标。这样只需要遍历数组一次，时间复杂度是 O(n)。

这几句话基本就把 Two Sum 的核心讲清楚了。

这道题真正要记住什么？

不要死记代码，要记住这个判断过程：

当前数字是多少？
↓
距离 target 还差多少？
↓
这个差值以前出现过吗？
↓
出现过：返回两个下标
没出现：保存当前数字和下标

以后看到这类题目时，可以优先考虑哈希表：

  • 查找两个数字是否满足某种关系；
  • 判断某个值之前是否出现过；
  • 需要快速查询数组中的历史元素；
  • 暴力解法存在大量重复查找。

今日刷题记录

题目：

Two Sum

核心数据结构：

Hash Map

核心公式：

complement = target - current number

时间复杂度：

O(n)

空间复杂度：

O(n)

最容易犯的错误：

先把当前数字存进 map，再检查 complement

正确顺序：

先检查，再存入

Grind 75 的第一道题并不难，但它建立了一个非常重要的刷题习惯：

不要只想着怎么得到答案，还要思考哪些重复操作可以被省掉。