两数之和：一遍扫描，一个记忆
把「找一对」翻转成「认一个见过的数」，O(n²) 的重复劳动就此消失。
高效解法只做一件事：每扫过一个数就把它「记住」，然后用一次 O(1) 的查找回答「它的补数我见过吗」。全程一遍扫描，时间 O(n)，空间 O(n)。
想象你在翻一本旧电话簿，想找出两个号码，使它们的和等于某个目标数字。你会一页一页地把两个号码两两相加去碰运气，还是边翻边把见过的号码记下来，等遇到「恰好能凑成目标」的那个时立刻认出来？
前者是每个新手的第一直觉——它正确，但会把同样的加法重复成千上万次。后者只需要一遍扫描：每到一个数，只问一句「它的补数，我见过吗」，用一张 O(1) 的查找表回答。
这篇文章会带你重走这条从直觉到最优的路：先看清暴力解法为什么重复，再完成一次关键的视角翻转，最后落成五行 Go 代码。读完之后你会理解，为什么高手看到这类「两两相加」的题，第一反应不是去配对，而是去建一张记忆表。
先明确问题
给你一个整数数组 nums 和一个目标值 target，请你在数组里找出两个下标 i 和 j（i ≠ j），使得 nums[i] + nums[j] 正好等于 target，然后返回这两个下标。
以示例为例：nums = [2, 7, 11, 15]，target = 9。因为 2 + 7 = 9，所以返回 [0, 1]。
这道题是 LeetCode 的第 1 题，也是几乎所有人的第一道题。它足够简单，因此几乎所有错误的认识都暴露得很充分——尤其是「暴力枚举够用」的错觉。
第一直觉：两两配对
最直接的想法是固定第一个数，把它和后面每一个数都加一次：2+7、2+11、2+15，都不对就固定第二个数，继续 7+11、7+15……直到找到一组相加等于 target 的。
在示例里，第一次比较 2 + 7 = 9 就命中了。看起来快得惊人——但请注意，命中的是运气。换一组不那么配合的数据：[3, 1, 4, 2, 7]，target = 6。3 要依次和 1、4、2、7 各加一次：3+1=4、3+4=7、3+2=5、3+7=10，全部落空。
更糟的在后面。轮到 1 的时候，它又要和 4、2、7 各加一次；轮到 4，又要和 2、7 各加一次。每一轮比较的结果都被直接丢弃，从不复用。n 个数一共要做 n(n−1)/2 次比较——这就是 O(n²)。
从第一个数开始，依次向后相加。
一个视角翻转：补数
暴力之所以重复，是因为它一直在问「我和谁相加等于 target」——这是一个从当前数出发、向后搜寻的问题，每次都要重新打量所有后面的数。
现在把这个问题翻转过来：x + y = target，等价于 y = target − x。也就是说，当我手上是 x 时，我真正要找的只有一个确切的数 y，它被 x 唯一决定。我把它叫做 x 的「补数」。
于是问题从「找一对」变成了「认一个见过的数」。2 的补数是 7，7 的补数是 2，11 的补数是 −2，15 的补数是 −6。我需要回答的问题，从「数组里有没有另一个数能和我凑成 9」，变成了「我见过的数里，有没有这个补数」。
视角「找一对」是 O(n²) 的循环；「认一个见过的数」是 O(1) 的查询。只换一个问法，复杂度就被写进了问题的形状里。
每个数只关心它的补数——一个由它唯一决定的数。
一遍扫描，加一个记忆
现在把「补数」和「记忆」拼起来：从左到右扫过数组，每扫到一个数 x，先查补数 target − x 在不在记忆里。在，就立刻返回答案；不在，就把 x 连同它的下标存进记忆，继续往后走。
以 [3, 1, 4, 2, 7]、target = 6 为例。扫到 3，补数是 3，记忆是空的，存入「3 → 0」；扫到 1，补数是 5，没见过，存入「1 → 1」；扫到 4，补数是 2，没见过，存入「4 → 2」；扫到 2，补数是 4——见过！它在下标 2。返回 [2, 3]。
每个数只做两件事：一次 O(1) 的查询，至多一次 O(1) 的存入。整个数组一遍扫完，总时间 O(n)。记忆表最坏情况下存下所有数，空间 O(n)。
为什么保证不漏？扫到第 i 个数时，记忆里已经存了前 i−1 个数。如果答案的补数存在于数组中，它必然落在前 i−1 个里，也必然被这次的查询找到；查不到，说明它尚未出现，我们把当前数存进去继续。每一步都不漏，归纳地，整个数组都不漏。
顺序的坑：先查，再存
上面那句「先查补数，再存自己」的顺序不是随口说的，它是一个真正的坑。
假设输入是 [2]，target = 4。如果先把当前数存进记忆，再查补数：存入「2 → 0」，然后查询补数 4 − 2 = 2——命中了，但它命中的是「自己」。返回 [0, 0]，两个下标相同，而题目要求 i ≠ j。错。
反过来，先查补数再存自己：此时记忆还是空的，查询补数 2 落空，然后把「2 → 0」存入。这才安全。规则一句话：记忆里永远只装「我已经真正看过的数」，而当前的自己，在查询的这一刻还不算「看过」。
复杂度，与它可以推广到哪里
时间 O(n)：一遍扫描，每个数一次查询、至多一次存入。空间 O(n)：记忆表最坏存下全部元素。这已经是最优——读入整个数组本身就要 O(n)。
这套「用补数 + 记忆消灭重复比较」的哲学可以走得很远。三数之和可以固定一个数，把剩下的问题降维成两数之和；判断数组里的最长连续序列，可以先问「我的前驱在不在」再决定是否扩张；更普遍的「记忆化」思想——把算过的结果存起来，下次直接取——也是同一种味道：用空间换掉重复计算。
直觉O(n²) 的重复，多半能用一个 O(n) 的记忆消掉。先问自己：我是不是在重复做已经做过的事？
五行 Go
func twoSum(nums []int, target int) []int {seen := map[int]int{}for i, x := range nums {if j, ok := seen[target-x]; ok {return []int{j, i}}seen[x] = i}return nil}
1seen 是一张「值 → 下标」的记忆表，一开始是空的。
2每一轮，i 是当前下标，x 是当前值。
3先查补数：target − x 在不在 seen 里。在，说明补数在前面的某处 j 出现过，直接返回 [j, i]。
4不在，就把当前值存进记忆：seen[x] = i。先查后存，正是上一节的坑。
总结
先查补数，再存自己。
- 暴力两两配对是 O(n²)，因为每一次比较的结果都被丢弃，从不复用。
- 补数视角把「找一对」翻转成「认一个见过的数」，把问题写进了 O(1) 查询的形状里。
- 一遍扫描 + 一张记忆表：查不到就存下自己，每个数至多查一次、存一次。