01先读懂这个概念
从一个双循环出发
给 a=[4,1,7,3] 和 target=10，要求返回两个不同位置，使数值相加为 10。直接枚举 i<j 最坏检查 n(n−1)/2 对。固定当前 value 后，另一个数并不任意：它必须等于 target−value。
因此需要一份『以前见过的值 → 它的下标』的表。扫描到 7 时 need=3，表中没有；扫描到 3 时 need=7，表中已有 7→2，于是返回 [2,3]。每次只查一个补数，不再重新扫描整个前缀。
哈希表不是一块不会冲突的魔法内存
键通过哈希函数映射到桶，不同键可能落进同一桶，这叫哈希冲突。正确的实现还会判断键是否相等，因此冲突影响性能，不应让 4 和 14 被当作同一个键。Python 的 dict 是键值表，set 只记录是否存在。
在哈希分布与装载控制良好时，查询、插入通常按期望 O(1) 分析；并非任意输入都有最坏常数保证。本课使用短整数键，暂不计长字符串哈希本身的长度成本。你现在不必实现哈希表，但需要知道它用额外空间换了查找效率。
02从具体数据开始手算
拿一个小输入，逐步手算
a=[4,1,7,3]，target=10；表只包含已经经过的位置。
| 当前 i / value | need | 查询前 seen | 动作 |
|---|---|---|---|
| 0 / 4 | 6 | {} | 没有 6，记入 4→0 |
| 1 / 1 | 9 | {4:0} | 没有 9，记入 1→1 |
| 2 / 7 | 3 | {4:0,1:1} | 没有 3，记入 7→2 |
| 3 / 3 | 7 | {4:0,1:1,7:2} | 找到下标 2，返回 [2,3] |
先查再写使表里的位置一定早于 i，因此不会用同一位置两次；找到的是一组合法答案，不保证某种字典序。
03把正确性的理由说清楚
这个索引为什么足够
- 扫描到 i 前，seen 中保存前缀 a[0:i] 里每个已出现值的某个下标。初始空前缀对应空表。
- 若 need 在 seen 中，两个位置不同且值之和等于 target。否则把当前值记进去，保持前缀索引的含义。
- 任意合法答案的一对下标可写成 j<i。扫描到较晚的 i 时，a[j] 必然已在表中，所以至少会找到一组答案。
04把刚才的思路写成代码
基础课用 Python 表达，先对照变量含义与执行顺序。后续算法课提供 Python、C++ 与 JavaScript 三种实现。
def two_sum(a, target):
seen = {}
for i, value in enumerate(a):
need = target - value
if need in seen:
return [seen[need], i]
seen[value] = i
return []代码里的每个关键决定
seen = {}- 键是已经出现的数值，值是该数值的下标；两者不能写反，否则无法按补数查。
if need in seen:- 查询键是否存在。必须在写入当前元素之前查询；a=[3]、target=6 时不能返回 [0,0]。
seen[value] = i- 如果同值已经出现，可以覆盖为最近下标；题目只需任意两个不同位置，这足够。若要返回所有配对，则需要保存更多下标信息。
05这些操作要付出多少代价
把工作量具体数出来
循环最多 n 次，每次一次哈希查询与一次插入，在上述哈希假设下总时间期望 O(n)。
表最多保存 n 个不同键值对，辅助空间 O(n)。与双循环的 O(1) 辅助空间相比，这正是时间与空间交换。
如果问题要求原始下标，先排序会改变位置关系；用哈希表可以保留原下标。有序输入则还可以使用下一节的双指针。
06用一个反例检查理解
先写入会把自己当作搭档
a=[3]，target=6。若先执行 seen[3]=0，再查询 need=3，就会错误返回 [0,0]；但这里只有一个位置。
怎样修正：先查询，成功就返回，失败才写入。a=[3,3] 时第二个 3 才能与第一个匹配，答案为 [0,1]。
07自己推一次，再做自测
再做一遍补数查询
手算 a=[2,5,2]、target=4。写出每轮查询前的 seen，解释最后为什么返回两个不同下标。
需要一点提示
第一轮需要 2，但表还是空的。
查看完整推导与答案
- i=0，need=2，空表未命中，写入 {2:0}。
- i=1，need=−1，未命中，写入 {2:0,5:1}。
- i=2，need=2，命中下标 0，返回 [0,2]。当前下标没有预先进入表。