LeetCode 1. 两数之和：哈希表的第一课，用空间换时间

题目与直觉

两数之和——从暴力到哈希的思维跃迁

LeetCode 1 是全站第一题：给定整数数组 nums 和目标值 target，找出和为目标值的两个整数的下标，返回下标数组。每个输入恰好有一个解，同一个元素不能用两次。

输入：nums = [2, 7, 11, 15], target = 9
输出：[0, 1]（nums[0] + nums[1] = 2 + 7 = 9）

直觉的第一反应：两层循环暴力枚举——每一对都试一次，nums[i] + nums[j] == target 就返回。这个写法人人会写，它不是错的，它只是 O(n²)——n=10000 时是 1 亿次比较。优化不是「换个写法」，是换一个问题。

换问题：从「找两个数」到「找一个数」

暴力解的本质：对每个 nums[i]，都在剩下的数里找 target - nums[i]——「两个数」的问题被循环拆成了「找一个数」。找到 target - nums[i] 用的是内层循环——内层循环在重复回答同一个问题：「X 在不在数组里」。

哈希表的入场：「X 在不在」这个问题，哈希表用 O(1) 回答——把已经见过的数放进哈希表，每遍历一个新数，问哈希表「target - 当前值 在不在」：

遍历 nums = [2, 7, 11, 15], target = 9
i=0: num=2, 补数=9-2=7, 表里没有 → 存 {2: 0}
i=1: num=7, 补数=9-7=2, 表里有 2（下标 0）→ 返回 [0, 1]

为什么存「补数查过了」就够：两个数 i 和 j，当遍历到 j 时，i 必然已经遍历过——「已见过的数」就是「所有可能的另一半」——不需要回头找，只需要向前问。

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

graph LR
    A[暴力 O(n²)<br/>内外两层找] -->|换问题| B[哈希 O(n)<br/>边遍历边问表]
    B --> C[时间 O(n) 空间 O(n)<br/>用空间换时间]

为什么哈希查找是 O(1)

哈希表的原理拆解：哈希表 = 数组 + 哈希函数——哈希函数把 key 映射成数组下标（hash(key) % capacity——「计算下标」是 O(1) 的算术）；数组下标访问是 O(1)。碰撞（collision）：两个 key 映射到同一下标——链地址法（同一下标挂链表——查找退化到链表长度——Python dict 用开放寻址——「好的哈希函数」让碰撞稀疏——哈希查找的 O(1) 是「平均 O(1)」，最坏退化 O(n)——「为什么 Python dict 是 O(1)」的底层解释。

两数之和的边界情况：同一个元素不能用两次——如果 target = 6、nums = [3, 3]——答案是 [0, 1]——「先查后存」的顺序保证：先查补数再存当前值——遍历到第一个 3 时表里没有 3（不会自己配自己）——遍历到第二个 3 时补数 3 在表里（找到第一个 3 的下标）——「查在存前」是这个解法的精妙之处——如果先存后查，target = 2 × nums[i] 时会错误地匹配自己。重复值与多解：题目保证唯一解——若允许多解（返回所有配对），一次遍历把所有匹配收集（「变体的方向」：返回所有配对、找出三个数（三数之和）、找出最接近的（三数之和最近）——「两数之和」是这一族问题的地基。

这个思想的延伸

「空间换时间」的普遍性：哈希表是「用空间换时间」的最典型代表——本质是「把计算结果记下来」：算过的东西存起来，下次直接查——「记忆化」的广义：DP 的 memo、缓存的 TTL、布隆过滤器的「可能存在」——「查表」思想的三层：精确查表（哈希表）、近似查表（布隆过滤器）、有序查表（二分/红黑树——log n 的代价换有序性）。

后续题目的延伸：两数之和 II（有序数组）：数组有序后，双指针 O(n) 时间 O(1) 空间（不需要哈希表——有序让「两端的和」可判断——「有序性」替代了「哈希表」——空间从 O(n) 降到 O(1)——「数据结构的选择取决于数据的性质」：无序用哈希、有序用双指针——三数之和：排序后固定一个数，剩下两个数用双指针——「两数之和的思想」在有序数组上的化身——三数之和 = 遍历 + 两数之和（双指针版）。工程中的应用：数据库索引（哈希索引 vs B+ 树索引——「等值查询」用哈希、「范围查询」用 B+ 树——两数之和的「在不在」就是等值查询）；缓存的键查找、分布式的一致性——「哈希查找 O(1)」是分布式系统的地基之一（一致性哈希篇的思想源头）。

哈希的底层与「两数之和」的工程化

哈希表的底层与工程化延伸。「哈希函数」的质量：好的哈希函数 = 均匀分布（「均匀」的意义（碰撞稀疏、桶负载均衡——「Python 的 hash」（对象哈希的可定制（hash——「可变对象不能做 key」的原理（值变了哈希变、找不到——「不可变做 key」的纪律（字符串、元组——「哈希的碰撞攻击」（恶意构造的碰撞（DoS——「SipHash」的随机化（Python 的哈希随机化——「碰撞攻击」的防御。「开放寻址 vs 链地址」的深度对比：链地址（Python 3.7 前——开放寻址（「探测序列」（线性探测的聚集（「聚集」的问题——「二次探测/双重哈希」的改进——「开放寻址的缓存友好」（连续内存——「Python 3.7 的紧凑 dict」（「紧凑布局」的优化——「稀疏数组→紧凑数组」的内存节省——「语言的实现细节」影响性能。「两数之和」的工程化：「数据库索引」的哈希索引（等值查询的 O(1)——「哈希索引的局限」（范围查询不行——「B+ 树」的范围优势——「MySQL 的哈希索引」（Memory 引擎——「InnoDB 的自适应哈希」（自动为热点页建哈希——「自适应哈希索引」（AHI——「热度检测」的自动——「工程中的哈希」：缓存键、路由分片、分布式一致性哈希（「一致性哈希」的延伸阅读（库内已有专文）——「两数之和」的工程影子：「两个系统找配对」（对账系统的配对（「对账的哈希」（键的配对——「对账」的 O(n) 化——「配对」的工程价值——「事务对账」（支付与订单的配对——「哈希」在对账的核心作用——「对账系统」的效率依赖哈希——「从算法题到对账系统」的迁移。「变体的延伸矩阵」：「两数之和 II（有序）」（双指针 O(1) 空间——「有序的双指针」——「167 题」（有序数组的两数之和——「首尾指针」（和大了右移、小了左移——「移动的证明」（「单调性」的利用——「双指针的正确性」——「与哈希的对比」（时间同 O(n)、空间 O(1) vs O(n)——「有序的前提」——「变体的矩阵」：两数之和（哈希）、II（双指针）、III（数据结构设计 add/find——「add 的数据结构选择」（计数哈希——「find 的两数组合」——「变体的难度梯度」——「核心思想的复用」：「用空间记录、用查找配对」——「复用」的深度思考。哈希的进阶总结：底层（哈希函数、碰撞、开放寻址、紧凑 dict）+工程（自适应哈希索引、对账配对）+变体矩阵（有序双指针、III 设计题）——「两数之和」教的是「在遍历中用哈希回答『在不在』」——这个模式的变体在「对账、缓存、索引」中无处不在——「第一题」的含金量在于它是「数据结构与工程」的第一个交汇点。

哈希的底层与「两数之和」的工程化延伸

哈希表的底层与工程化延伸。「哈希函数」的质量：好的哈希函数 = 均匀分布（「均匀」的意义（碰撞稀疏、桶负载均衡——「Python 的 hash」（对象哈希的可定制（hash——「可变对象不能做 key」的原理（值变了哈希变、找不到——「不可变做 key」的纪律（字符串、元组——「哈希的碰撞攻击」（恶意构造的碰撞（DoS——「SipHash」的随机化（Python 的哈希随机化——「碰撞攻击」的防御。「开放寻址 vs 链地址」的深度对比：链地址（Python 3.7 前——开放寻址（「探测序列」（线性探测的聚集（「聚集」的问题——「二次探测/双重哈希」的改进——「开放寻址的缓存友好」（连续内存——「Python 3.7 的紧凑 dict」（「紧凑布局」的优化——「稀疏数组→紧凑数组」的内存节省——「语言的实现细节」影响性能。「两数之和」的工程化：「数据库索引」的哈希索引（等值查询的 O(1)——「哈希索引的局限」（范围查询不行——「B+ 树」的范围优势——「MySQL 的哈希索引」（Memory 引擎——「InnoDB 的自适应哈希」（自动为热点页建哈希——「自适应哈希索引」（AHI——「热度检测」的自动——「工程中的哈希」：缓存键、路由分片、分布式一致性哈希——「两数之和」的工程影子：「两个系统找配对」（对账系统的配对——「对账的哈希」（键的配对——「对账」的 O(n) 化——「配对」的工程价值——「事务对账」（支付与订单的配对——「哈希」在对账的核心作用——「对账系统」的效率依赖哈希——「从算法题到对账系统」的迁移。「变体的延伸矩阵」：「两数之和 II（有序）」（双指针 O(1) 空间——「有序的双指针」——「167 题」（有序数组的两数之和——「首尾指针」（和大了右移、小了左移——「移动的证明」（「单调性」的利用——「双指针的正确性」——「与哈希的对比」（时间同 O(n)、空间 O(1) vs O(n)——「有序的前提」——「变体的矩阵」：两数之和（哈希）、II（双指针）、III（数据结构设计 add/find——「add 的数据结构选择」（计数哈希——「find 的两数组合」——「变体的难度梯度」——「核心思想的复用」：「用空间记录、用查找配对」——「复用」的深度思考。哈希的进阶总结：底层（哈希函数、碰撞、开放寻址、紧凑 dict）+工程（自适应哈希索引、对账配对）+变体矩阵（有序双指针、III 设计题）——「两数之和」教的是「在遍历中用哈希回答『在不在』」——这个模式的变体在「对账、缓存、索引」中无处不在——**「第一题」的含金量在于它是「数据结构与工程」的第一个交汇点。

小结

两数之和的完整解法路径：暴力 O(n²)（正确但慢——每对都试）→ 换问题（「找两个数」拆成「找一个数」——内层循环的重复劳动被识别）→ 哈希表 O(n)（已见过的数进表、对每个新数查补数——「查在存前」防自配）→ O(1) 查找的原理（哈希函数+数组下标——平均 O(1)、碰撞与链地址法）→ 思想的延伸（有序数组用双指针省空间、三数之和的套娃、工程中的哈希索引）。这道题的教学价值远超题目本身：它是「优化 = 换一个问题 + 换一个数据结构」的第一课——暴力解不是罪，它是优化的起点；优化的本质是识别「重复劳动」，然后为这个劳动找一个更快的工具——哈希表、双指针、记忆化，都是不同场景下「更快回答同一个问题」的工具。

面试时被问到两数之和，说出 O(n²) 不是失败——说出「内层循环在重复回答『在不在』的问题」才是分水岭——然后哈希表就是水到渠成的答案。