两数之和算法详解：从暴力枚举到哈希表的优化进阶

1. 题目到底在问什么

1.1 原题信息与核心考点

两数之和（Two Sum）这道题，只要你刷过 LeetCode，几乎不可能绕开它。它是 HOT 100 的开门题，也是很多人口中的“算法刷题第一站”。题目本身不长：给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回它们的数组下标。你可以假设每种输入只会对应一个答案，但是数组中同一个元素不能使用两遍。

这句话里藏着两个关键信息点，很多新手会忽略。第一是“返回下标”，不是返回值。这意味着你不能简单地把数组排序然后取首尾，因为排序会把下标打乱。第二是“同一元素不能使用两遍”，这直接否定了 nums = [3]、target = 6 这种场景下返回 [0,0] 的自欺欺人写法。题目虽然保证了只有一个答案，但这两个约束条件决定了解题方向：你必须在尽量少遍历的前提下，同时记住“值”和“位置”两个信息。

这道题为什么被放在 HOT 100 第一位？不是因为难，恰恰是因为它足够简单、足够经典。它考察的是最基础的哈希表思想，而这种思想在后面的很多题目里都会反复出现。三数之和、四数之和、和为 K 的子数组、最长连续序列，本质上都在用“空间换时间”这个思路。所以把这一题吃透，不光是搞定一道题，更是为整个 HOT 100 刷题之旅打地基。

1.2 适合什么样的人来学

如果你是刚开始刷算法题的萌新，这道题是你建立信心的好起点。它不需要什么高深的数据结构基础，只要理解数组遍历和字典（HashMap）的基本操作就能上手。如果你已经有了一定的刷题量，这道题同样值得重新审视——能不能写出一次遍历的版本？能不能解释清楚为什么要“先查后存”而不是“先存后查”？能不能聊清楚哈希冲突时底层是怎么处理的？这些追问会让简单的题目也显得有深度。

我见过不少同学，这道题能 AC 但讲不清楚原理，结果面试时被面试官多问一句就卡住了。两数之和在面试里出现的频率极高，而且面试官往往会从这道题延伸出变体，比如“如果数组有序怎么办”“如果要求返回所有不重复的组合怎么办”。所以这篇内容不光是讲题，还会把背后的思维模型、边界条件、面试追问都拆开揉碎了讲清楚。

2. 三种解法逐个拆解

2.1 暴力枚举：最直白的思路

拿到这道题，第一反应自然是嵌套循环。外层循环固定一个数 nums[i]，内层循环去后面找有没有 target - nums[i]，找到了就直接返回两个下标。

python复制def two_sum_brute(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]
    return []

这个解法最大的优点是直觉、不容易写错，而且不需要任何额外空间。但问题是时间复杂度是 O(n²)。当 n 是 10000 时，内层的平均比较次数是 5000 次，总运算量大约是 5000 万次；当 n 变成 100000 时，运算量直接跳到约 50 亿次，这在实际场景里已经是不可接受的了。

我在给初学者讲这道题时，经常拿“聚会找朋友”来打比方：暴力法就是你站在人群里，一个一个去问“你是不是和我凑成目标数的人”。假设现场有 100 个人，你要问接近 5000 次才能判断完；如果有 10000 个人，这个询问次数会膨胀到千万级别。直觉上你就知道这不是个好办法。

暴力法虽然时间复杂度高，但它有一个非常重要的价值：它是最可靠的兜底方案。有些人在面试时一上来就追求最优解，结果写了一半手抖了，反而连暴力解都没写出来。我的建议永远是：先想暴力，再想优化。暴力解写出来至少能保底，而且它给了你分析问题的时间——你在写循环的时候，往往就能意识到“我每次都在重复查找同一个值”，这自然就会引导你想到哈希表。

2.2 排序后双指针：看似巧妙却容易踩坑

排序加双指针是一个经典组合，很多“找两个元素满足某种关系”的题都能用它解决。思路很简单：先把数组排序，然后一左一右两个指针往中间移动。如果两个指针指向的元素之和大于 target，右指针左移；如果小于 target，左指针右移。

python复制def two_sum_pointer(nums, target):
    sorted_nums = sorted(nums)
    left, right = 0, len(sorted_nums) - 1
    while left < right:
        cur = sorted_nums[left] + sorted_nums[right]
        if cur == target:
            # 这里能返回原下标吗？不能！
            return [left, right]
        elif cur < target:
            left += 1
        else:
            right -= 1
    return []

这个解法的时间复杂度是 O(n log n)，比暴力法好很多，空间复杂度取决于排序实现。但注意，前面强调过：这题要求返回原始数组的下标。排序之后下标就乱了，你无法直接从排序数组的位置拿到原数组的下标。虽然可以用“存成 (值, 原下标) 的列表再排序”来补救，但代码写起来明显麻烦。

那这个解法还有没有意义？有，而且意义很大。它会引出下面要讲的一个关键思维：如果题目给你的数组本身就是有序的，或者允许你直接返回数值而不是下标，那双指针就是比哈希表更省空间的方案。比如后面要说的两数之和 II，就是 LeetCode 167 题，输入的数组是有序的，官方推荐解法就是双指针，空间复杂度 O(1)。所以这道题的几种解法不是谁替代谁的关系，而是互相补充，让你在不同约束条件下能快速选择合适工具。

2.3 哈希表：空间换时间的标准答案

哈希表解法才是这道题真正的主角。核心思路一句话：遍历数组时，用一个字典记录已经见过的数字和它的下标，每到一个新数字，就检查一下 target - 当前数字 是不是已经在字典里了。如果在，直接返回结果；如果不在，把当前数字存进字典。

这里我用一个很生活化的类比来解释：假设你在参加一个配对活动，每个人手里拿一个数字牌，目标是找到另一个手里数字牌能和自己凑成 target 的人。哈希表方案就是：你每遇到一个人，先看看自己随身带的记事本上有没有写着能和自己配对的那个数字；如果记事本上没有，就把自己的数字写在记事本上，然后继续去找下一个人。每个人都只需要翻一次记事本，不用回头问已经见过的人。

为什么这个方案是 O(n) 的时间复杂度？因为字典的查找和插入在平均情况下都是 O(1)。你把“和后面每一个人比较”这件事，转化成了“查一次记事本”。查询一次是常数时间，n 个人就是 O(n)。代价是你需要准备一本记事本，也就是额外的 O(n) 空间。

我个人非常喜欢这个思路，因为它精准地体现了“空间换时间”的核心价值。很多算法优化本质上就是在做这种转化：你要么多花时间重新计算，要么多花空间把算过的结果存下来。两数之和用哈希表，就是最经典的示范。

3. 哈希表方案的代码实现与细节

3.1 Python 实现与“先查后存”

Python 里用字典实现哈希表，配合 enumerate 可以同时拿到下标和值，代码非常简洁：

python复制def two_sum(nums, target):
    seen = {}
    for i, num in enumerate(nums):
        need = target - num
        if need in seen:
            return [seen[need], i]
        seen[num] = i
    return []

每次循环，先检查 need 是否已经在 seen 里。如果在，说明之前遍历到了这个需要的数，直接返回它的下标和当前下标。如果不在，把当前数字存入字典。注意是先查后存，顺序很重要。如果先用一个循环把所有数字存进字典，再用第二个循环查找，就属于“两遍哈希表”的写法，那样也没问题，但必须额外判断“找到的下标不能是当前下标自己”。而“先查后存”天然规避了这个麻烦——因为你还没有把当前数字放进去，查到的必然是之前出现过的数字。

很多人会有疑问：题目说数组里同一个元素不能使用两遍，那我如果写成“先存后查”是不是一定会出错？不一定。只有在数组中恰好存在一个值等于 target 一半的数字，且它只出现一次时，才会出问题。比如 nums = [2]、target = 4，如果先存后查，遍历到 2 时查 4 - 2 = 2，字典里已经有了刚存进去的 2，于是返回 [0, 0]，这就不符合题意了。虽然题目保证有解，不会出现这种极端情况，但在工程实现里，依赖题目的“保证”不是好习惯。所以一律用“先查后存”是最稳妥的。

3.2 Java 和 Go 的写法对比

Java 版本的思路完全一样，只是用 HashMap 来代替 Python 的字典：

java复制public int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        int need = target - nums[i];
        if (map.containsKey(need)) {
            return new int[]{map.get(need), i};
        }
        map.put(nums[i], i);
    }
    return new int[0];
}

Go 的写法也很有意思，它的 map 访问可以同时返回值和是否存在，代码风格很简洁：

go复制func twoSum(nums []int, target int) []int {
    seen := make(map[int]int)
    for i, num := range nums {
        if j, ok := seen[target-num]; ok {
            return []int{j, i}
        }
        seen[num] = i
    }
    return nil
}

这三份代码逻辑完全等价，但有几个细节值得注意。Java 中如果 nums 包含非常大的整数，target - nums[i] 可能会有溢出问题，例如 nums[i] 接近 Integer.MAX_VALUE 且 target 是负数的情况。虽然 LeetCode 的测试数据很少构造这种极端场景，但面试时可以主动提出来，说配合 long 类型来避免溢出，这会让面试官觉得你考虑问题全面。Go 和 Python 的整数类型则没有这个担忧，因为它们是自动扩展的。

3.3 字典的键冲突问题真的不用管吗

用哈希表还有一个容易被忽略的底层问题：不同数字哈希到字典同一个位置怎么办？这个问题在刷题阶段几乎不用考虑，因为 Python 的字典和 Java 的 HashMap 都内置了冲突处理机制。Python 使用开放寻址，Java 使用链地址法（在链表长度超过阈值后转为红黑树），语言层面的实现已经帮你处理好了。

但如果你在面试中被问到“哈希表冲突了怎么办”，至少要能说出一种处理方式。最简单的回答就是“拉链法”：把哈希到同一个位置的所有元素用链表串起来，查找时需要遍历这个链表。这会影响哈希表最坏情况下的时间复杂度——如果所有元素都冲突，查找会退化成 O(n)。不过正常的哈希函数设计会让元素分布足够均匀，平均复杂度依然是 O(1)。

这也是为什么我说两数之和不是一道“做出来就行”的题。它背后的哈希表原理，直接对应着很多实际开发中的设计决策。比如缓存系统的 key 设计、数据库索引的选择、分布式系统里的一致性哈希，都是类似思维的延伸。把哈希冲突、空间换时间这些概念吃透，比单纯记住这道题的解有价值得多。

4. 边界情况与高频变体

4.1 面试官最爱问的边界条件

两数之和的官方题解虽然短，但边界情况一点都不少。我把常见的问题整理成一张速查表，方便你刷题和面试前快速过一遍：

我自己在实际讲解中发现，初学者最容易翻车的就是“先查后存”和“先存后查”的问题。比如 nums = [3, 2, 4], target = 6，正确答案是 [1, 2]，对应 2 和 4。但如果你第一遍先把所有元素存进字典，第二遍再从第一个元素开始找，找到 3 时查 6 - 3 = 3，于是认为下标 0 和下标 0 都不需要再找，直接返回 [0, 0]——错得离谱。所以我的建议是在代码里永远遵循：查不到再存，查到了直接返回。这个顺序记熟，能避免一系列低级错误。

4.2 从两数之和延伸到三数之和

刷 HOT 100 的最大好处就是你会发现题目之间是有血缘关系的。两数之和解决之后，紧接着你很可能遇到三数之和（LeetCode 15 题）。题目让你找到所有不重复的三元组，使得三个数之和为 0。

三数之和就不能直接套用两数之和的哈希表写法了。因为“所有不重复的”这个要求，让基于哈希表的去重变得异常繁琐。你不仅要考虑结果不重复，还要小心同一个元素被重复使用。更简洁的做法是排序加双指针：先排序数组，然后固定一个数字，在它后面的区间里用双指针找另外两个数。固定数字时跳过重复值，双指针移动时也要跳过重复值，这样才能保证三元组不重复。

这个转变非常值得体会：两数之和用哈希表是因为要返回下标且数组无序；三数之和面临“去重”的新约束，排序反而成了更好的预处理手段。所以遇到算法题，不要迷信某一种解法，要根据题目的具体要求灵活切换。这也是我反复强调的：把一道题做透，比草草刷十道题更有价值。

4.3 有序数组版与子数组问题

两数之和在 HOT 100 里还有几个“近亲”。第一个是两数之和 II（LeetCode 167），输入数组已经有序，这时双指针就是最优解法，空间复杂度可以做到 O(1)。面试官如果在两数之和后追问“如果数组有序你怎么做”，你答出双指针基本就过关了。

第二个近亲是求和为 K 的子数组（LeetCode 560），它问的是数组中有多少连续子数组的和等于 K。这道题看起来和两数之和八竿子打不着，但核心思路惊人的一致：用前缀和数组 pre[i] 表示从开头到第 i 个元素的和，那么 pre[j] - pre[i] 就是区间 (i, j] 的和。想让这个区间和等于 K，就是在遍历时不停地查“之前有没有出现过 pre - K 这个前缀和”。遇到这一题时你会有一种强烈的既视感：这不就是把两数之和的 target 换成了前缀和的差值吗。

所以我会说，两数之和是一把钥匙。它打开的门后面，站着一大堆“看起来不太一样，思路却完全同源”的题。你在 HOT 100 里刷得越多，越能体会这种“万变不离其宗”的乐趣。

5. 这套题怎么刷才有效

5.1 HOT 100 的整体刷题策略

我知道很多人的刷题状态是：打开 HOT 100，从第一题开始，一题一题往后做。两数之和能轻松 AC，但到第三题无重复字符的最长子串就开始卡壳，到第十题正则表达式匹配直接心态崩了，然后放弃。所以我想认真聊聊 HOT 100 到底应该怎么刷。

我的建议是做“三轮刷题法”。第一轮按顺序刷，但给自己设一个硬性规定：一道题最多思考 45 分钟，想不出来就去看题解，看完题解后合上答案自己重写一遍，能独立 AC 才算过。如果看了题解还写不出来，画个标记，隔天再看一遍题解，再重写一遍。这一轮的目的是建立全面的题型认知，不是让你证明自己有多聪明。

第二轮按标签刷。比如先把哈希表相关的题集中刷一遍，再把双指针相关的一起刷。这样做的好处是强化对不同数据结构、不同算法思想的理解。你会发现两数之和和和为 K 的子数组之间的共通性，会理解为什么有的题适合排序，有的题必须保持原数组顺序。

第三轮是复习轮。只做第一轮和第二轮中标过记号的题，每道题用尽量短的时间写出来。这一轮最好在面试前一到两周进行，目的是把短暂记忆转化为长期记忆。我个人的经验是：间隔复习比连续复盘效果至少好两倍。同一天把一道题重写十遍，不如隔三天写一遍、隔七天再写一遍。

5.2 我在这个题上的几个认知升级

说来惭愧，我第一次做两数之和时，用的就是暴力法，而且 AC 之后还觉得很得意。后来看了官方题解才知道有哈希表的写法。但我当时只是把题解抄了一遍，过了两个星期再让我写，我居然写不出来了。后来我总结出三个原因。

第一个原因是我不理解“为什么”。我只记住了“要用字典”，但没有真正想明白“字典在这里到底解决了什么问题”。直到我把暴力法的过程在脑子里复盘了一遍，才意识到：暴力法每一次内层循环都在重复查找同一个目标值，而哈希表把这种反复查找变成了 O(1) 的查询。理解了这一点，就不需要背代码，自然能推导出来。

第二个原因是我不重视边界条件。我总认为题目说“只有一种答案”就可以放心大胆地写。但当我自己开始尝试封装工具函数时，发现真实场景中根本不会有这种保证。后来我给自己的代码都加了“找不到就返回空”的保护逻辑，表面上看起来是多余的，实际上能避免很多线上事故。

第三个原因是我不会举一反三。刷完两数之和，我直接跳到下一题，完全没有去联想它和后续题目的关联。直到我刷到和为 K 的子数组，发现解法里又是“前缀和加哈希表”，才意识到如果早一点把两数之和的解法吃透，后面这些题都会轻松很多。从那以后，我每刷一道题，都会停下来想一想：这道题能不能用同一个思路改一改？这题和之前哪道题是“近亲”？这个习惯让我的刷题效率至少翻了一倍。

5.3 面试时怎么答这道题

最后聊一点实战经验。两数之和在面试里的出场率极高，但不一定是以原题的形式出现。有些面试官会让你直接写，有些会变着花样追问。我遇到过最典型的一个追问是：“如果这个数组特别大，装不进内存怎么办？”这个问题其实是在考察大规模数据的处理思维。如果是分布式场景，你可以把数组分发到多台机器上，每台机器对局部数据用哈希表，然后再汇总判断结果是否需要跨机器配对。如果是单机内存不足，可以考虑分块加载，或者用外部排序加二分查找的方式。

另一个追问是：“如果不要求下标，只要求判断是否存在两个数，能不能不用额外空间？”这时你可以先对数组排序再用双指针，空间复杂度 O(1) 就达标了。如果你能主动说出“对于有序数组，双指针是最优解”，再提到“无序数组要返回下标，哈希表更合适”，面试官基本就会满意了。

还有一个很常见的要求是：“你写一段测试用例，验证你的代码是正确的。”不要只写正例，最好把负例也覆盖到。比如 nums = [1, 2, 3]、target = 7，返回空；比如 nums = [3, 3]、target = 6，返回 [0, 1]。能主动写出边界测试，这个细节在面试中非常加分。

回到刷题本身。两数之和只是 HOT 100 的第一题，但它足够代表整个系列的核心学习方法：理解思路而不是背代码，关注边界而不是只看正例，学会延伸而不是做完就跑。把这个节奏把握住，后面那 99 题，你会在不断复现“两数之和的思考方式”中，越刷越顺手。