1. 两数之和 (Easy)

专题归类： 01-哈希表 LeetCode 链接： https://leetcode.cn/problems/two-sum/

---

在线做题： 写 Python 代码并运行 · Java 跳转 LeetCode

题目描述

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

你可以假设每种输入只会对应一个答案（即一定有解，且解唯一）。但是，数组中同一个元素不能使用两遍。

示例：

输入：nums = [2, 7, 11, 15], target = 9
输出：[0, 1]
解释：因为 nums[0] + nums[1] == 9

补充说明：

• 数组长度范围：2 <= nums.length <= 10^4
• 数值范围：-10^9 <= nums[i] <= 10^9
• 保证有且仅有一组有效答案

---

题目详细分析

数据范围含义：

• 数组长度最大 10^4，O(n^2) 的暴力解法会达到 10^8 次操作，在 LeetCode 上会超时。因此需要 O(n) 或 O(n log n) 的解法。
• 数值范围达到 ±10^9，说明两数之和可能达到 ±2×10^9，在 32 位整数范围内没有问题，不需要考虑大数溢出。
• “同一个元素不能使用两遍”意味着不能自己加自己，例如 target=6, nums=[3] 不能返回 [0,0]。

输入输出特征：

• 输入是无序整数数组，返回的是下标数组（长度为 2）。
• 题目保证有唯一解，因此不需要处理无解的情况。

边界条件：

• 最短数组长度为 2，不存在不足 2 个元素的情况。
• 可能有负数，所以 target - num 可能大于 num 本身。
• 可能有重复值，例如 nums = [3, 3], target = 6，返回 [0, 1]，但两个 3 是不同位置的。

隐藏条件：

• “唯一解”本身就是一个重要信息——找到后就可以立即返回，不需要继续遍历。
• 返回的是下标而非值，因此排序后不能直接返回原下标，需要记录映射关系。

---

小白版直白理解

想象你在参加一个派对，每个人身上贴着一个数字。主持人说：“谁身上的数字加起来等于 9？“你需要找到这两个人。

笨办法（暴力法）： 你一个一个地问每一个人：“你身上数字是多少？“然后去问其他人有没有人和他加起来等于 9。这个办法很慢——如果派对有 100 个人，最多要问 100×100 = 10000 次。

聪明办法（哈希表法）： 你准备一个记事本。每见到一个人，你在记事本上记下”要找 XX 号人”。比如第一个人身上是 2，你记下”需要找 7”。然后第二个人来了身上是 7，你翻开记事本一看——“需要找 7”，找到了！你们俩加起来就是 9。

这个方法只需要在派对上走一圈，每见一个人查一下记事本，O(n) 时间搞定。

---

解题思路

思路一：暴力枚举（不推荐）

最直接的想法：两层循环，枚举所有可能的组合，检查两数之和是否等于 target。

但时间复杂度 O(n

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

思路二：两遍哈希表

第一遍遍历：将所有元素的值和下标存入哈希表（值 → 下标）。 第二遍遍历：对每个元素 nums[i]，检查 target - nums[i] 是否在哈希表中，且下标不是 i。

需要额外处理”不能重复使用同一元素”的问题。

def twoSum(nums, target):
    # 第一遍：建立值到索引的映射
    mapping = {}
    for i, num in enumerate(nums):
        mapping[num] = i
    
    # 第二遍：查找互补元素
    for i, num in enumerate(nums):
        complement = target - num
        if complement in mapping and mapping[complement] != i:
            return [i, mapping[complement]]

思路三：一遍哈希表（推荐）

核心洞察：不需要把所有元素先存进去再查，可以边遍历边查找。

遍历到元素 num 时，检查 complement = target - num 是否已经出现在哈希表中：

• 如果出现过，说明之前遍历过的某个元素和当前元素正好凑成 target，直接返回。
• 如果没出现过，把当前元素存入哈希表，供后面的元素查。

这样做的好处是：一次遍历完成，且天然不会出现同一元素用两次的情况（因为当前元素还没存进哈希表）。

def twoSum(nums, target):
    """
    一遍哈希表解法
    - seen: 记录已遍历过的 {值: 下标}
    - 对每个元素 num, 检查 target - num 是否已在 seen 中
    """
    seen = {}
    for i, num in enumerate(nums):
        complement = target - num
        if complement in seen:
            return [seen[complement], i]
        seen[num] = i

---

易错点

• 重复元素混淆： 如果 nums = [3, 3], target = 6，用两遍哈希表时，第二遍遍历到第一个 3，查到的 mapping[3] 是 1（第二个 3 覆盖了第一个），但检查 mapping[complement] != i 会跳过，导致漏解。一遍哈希表没有这个问题。
• 负数处理： target 可能是负数，complement = target - num 可能大于 num，不要假设 complement 一定比 num 小。
• 提前返回： 找到解后立即 return，不要继续循环，否则可能覆盖结果。
• 哈希表覆盖： 用两遍哈希表时，如果有重复元素，后面出现的会覆盖前面的下标。一遍哈希表不会遇到这个问题。

---

框架提炼

哈希表辅助查找模板：

当问题需要在遍历过程中”回头看”已处理过的元素时，可以用哈希表记录历史信息，将查找从 O(n) 降到 O(1)。

def xxx_problem(nums, target):
    # 1. 初始化哈希表
    seen = {}
    
    # 2. 遍历元素
    for i, num in enumerate(nums):
        # 3. 检查互补条件是否满足
        complement = need_to_find(num, target)  # 不同问题不同计算
        if complement in seen:
            # 4. 找到了，处理结果
            return process_result(seen[complement], i)
        # 5. 记录当前元素供后续使用
        seen[num] = i

适用场景特征：

• 需要查找两元素之间的关系（和、差、积等）
• 可以边遍历边记录
• 只需要一次遍历就能得到结果

---

关联题目

• 15-三数之和 — 从两数之和扩展到三数之和，排序 + 双指针解决，去重成为新增的难点
• 18-四数之和 — 进一步扩展到四数之和，排序 + 双指针嵌套，剪枝优化更复杂
• 167-两数之和 II - 输入有序数组 — 同样是两数之和，但输入已排序，可以用双指针 O(1) 空间解决，不需要哈希表