1. 题目拆解为什么这道题被称作“梦开始的地方”两数之和——LeetCode题库的第1题无数人刷题生涯的第一道坎。我在带新人入门算法时几乎每次都会从这道题开始讲起。原因很简单它足够简单以至于能让你快速建立信心但它又足够深刻背后藏着哈希表、时间复杂度分析、空间换时间这些贯穿整个算法学习的关键思路。更现实的一点是这道题在面试中的出场率高得离谱尤其是针对校招和初级岗位。题目本身非常直白给定一个整数数组nums和一个整数目标值target请你在该数组中找出和为目标值的那两个整数并返回它们的数组下标。你可以假设每种输入只会对应一个答案但是数组中同一个元素不能使用两遍。换成人话就是有一串数字你告诉我一个目标值我去这串数字里找两个数让它们加起来正好等于目标值然后把这两个数在数组中的位置告诉你。这里有两个容易被忽略的约束条件需要仔细揣摩。第一“只有一个答案”意味着这道题不需要处理多个解的情况你找到一对儿就能收工这大大简化了实现逻辑。第二“同一个元素不能使用两遍”这句话看起来是废话但它其实是在防止一种低级错误比如target 6数组是[3, 3]你不能说“我用下标0的那个3加上下标0的那个3等于6”因为这是同一个元素被用了两遍正确结果应该是[0, 1]。在真正动手写代码之前我想先聊一聊这道题的核心难点。这道题作为第1题天然带着“新手劝退”和“老手回味”的双重属性。新手容易一头扎进暴力解法里觉得能跑就行而老手看到这道题想的却是如何在各种变体中快速定位最优解。它的核心难点不是“怎么找到答案”而是“怎么更快地找到答案”——这里就涉及到了算法学习中最基本也最重要的一组概念时间复杂度和空间复杂度。2. 从暴力解法说起为什么能用但不宜多用2.1 暴力枚举的基本逻辑最朴素的想法是什么两层循环。外层循环固定第一个数内层循环遍历它后面的所有数逐一检查两个数的和是否等于target。这是一个零思考成本的思路几乎不需要任何数据结构知识只要会写for循环就能实现。public int[] twoSum(int[] nums, int target) { for (int i 0; i nums.length; i) { for (int j i 1; j nums.length; j) { if (nums[j] target - nums[i]) { return new int[] { i, j }; } } } return new int[] {}; }注意内层循环从i 1开始而不是从0开始。这既避免了i和j指向同一个元素的情况也避免了两层循环找到同一对数字的重复劳动。比如数组[2, 7, 11, 15]i 0时检查2 7等到i 1时就没必要再去检查7 2了因为它们在数学上是同一对组合。2.2 时间复杂度推演当数据量变大之后暴力解法的时间复杂度怎么算外层循环要跑n次n是数组长度内层循环平均跑n/2次总的比较次数大约是n * n / 2用大O符号表示就是O(n^2)。这意味着什么我用一组具体数字来展示假设数组长度n 1000暴力解法大约需要做 50 万次比较当n 10000时这个数字变成了 5000 万当n 100000时是 50 亿次。而哈希表解法在同样规模下只需要做大约n次操作也就是 10 万次左右。差距就在这里体现出来了——从 50 亿到 10 万跨越了五个数量级。我在实际开发中遇到过一个真实的类似场景不是算法题而是一个用户标签匹配功能。两个用户集合做两两匹配当时直接写了双重循环上线后数据量一上来接口响应直接飙到 8 秒后来改造成哈希索引才压到 200 毫秒以内。这类问题在 LeetCode 上叫“两数之和”在真实业务中叫“双层循环性能瓶颈”本质上是一回事。当然暴力解法也不是一无是处。它的空间复杂度是O(1)也就是除了输入的数组本身不需要额外的内存空间。当数据量很小比如n 100的时候暴力解法和哈希表解法的实际执行时间差距几乎可以忽略不计但代码却简单得多。所以我说“能用但不宜多用”——在算法题里你需要展示自己的思考深度在实际代码中你需要考虑后续的数据增长趋势两者都指向同一个结论暴力解法只适合作为理解题意的起步不适合作为最终答案。3. 哈希表解法空间换时间的最经典实践3.1 核心思路用“补数”代替“求和”暴力解法慢就慢在每次都要遍历整个数组去寻找搭档。那我们换个思路能不能把遍历过的元素记录下来下次直接查询这里引入一个“补数”的概念。对于数组中的每个元素nums[i]如果它真的存在于一个有效解中那么它的搭档必然是target - nums[i]。所以我们不需要在每一轮都做两层循环而是只需要做一件事检查target - nums[i]之前有没有出现过。这个思路的第一步是建立一张哈希表键Key存数组元素的值值Value存这个元素在数组中的下标。然后从头遍历数组对于当前元素先在哈希表里查一下target - nums[i]是否存在如果存在说明之前遍历过的某个元素和当前元素正好凑成目标值直接返回两个下标。如果不存在把当前元素的值和下标放进哈希表然后继续遍历下一个元素。这个过程中有一个非常关键的顺序问题必须“先查询再插入”。我强调这一点是因为很多初学者在这里栽过跟头。如果先把当前元素放入哈希表再查询补数那么当数组中出现两个相同值的元素时就可能查询到当前元素自身。举例来说nums [3, 2, 4]target 6如果先把3放进去再查询查到target - 3 3存在就会错误地返回[0, 0]而不是正确答案[1, 2]。3.2 两遍哈希 vs 一遍哈希到底差在哪哈希表解法又细分为两遍哈希和一遍哈希两种写法。两遍哈希的意思是第一遍遍历整个数组把所有元素都放入哈希表第二遍再遍历数组逐个查找补数。这种写法逻辑上更直观也更容易想到但存在一个隐藏的坑——重复元素处理。比如nums [3, 3]target 6。第一遍构建哈希表时因为键不能重复后一个3会覆盖前一个3的下标哈希表最终存的是{3: 1}。第二遍遍历时i 0查到target - 3 3在哈希表中对应下标是1返回[0, 1]结果正确。但这里需要额外加一个判断查到的下标不能和当前下标相同。比如nums [3]target 6第一遍建表存下{3: 0}第二遍i 0时查到下标0如果不加判断就会错误返回[0, 0]。一遍哈希则直接在遍历过程中边查边存。这种方式更优雅因为它在查找的同时完成了建表平均情况下遍历到一半左右就能找到答案而且天然规避了“同一下标匹配自身”的问题——因为当前元素还没有被放进表中查到的补数必然是之前已经遍历过的元素而不是当前元素。两遍哈希的代码长这样public int[] twoSum(int[] nums, int target) { MapInteger, Integer map new HashMap(); for (int i 0; i nums.length; i) { map.put(nums[i], i); } for (int i 0; i nums.length; i) { int complement target - nums[i]; if (map.containsKey(complement) map.get(complement) ! i) { return new int[] { i, map.get(complement) }; } } return new int[] {}; }一遍哈希的代码更简洁public int[] twoSum(int[] nums, int target) { MapInteger, Integer map new HashMap(); for (int i 0; i nums.length; i) { int complement target - nums[i]; if (map.containsKey(complement)) { return new int[] { map.get(complement), i }; } map.put(nums[i], i); } return new int[] {}; }注意一遍哈希返回时先返回map.get(complement)再返回i因为查到的那个元素在数组中更靠前。这个顺序不能写反否则虽然不影响“找对了一对数”这个事实但会影响下标的排列是否符合题目要求。我见过不少人在这个细节上被测试用例卡住。3.3 复杂度量化分析这里我直接给出一组复杂度对比数据方便你直观理解差异解法时间复杂度空间复杂度适合场景暴力枚举O(n^2)O(1)数组极小n 100两遍哈希表O(n)O(n)思路演示、教学场景一遍哈希表O(n)O(n)面试与竞赛首选哈希表在查询上的平均时间复杂度是O(1)这让整体算法从嵌套循环降级为单层循环时间复杂度从O(n^2)降为O(n)。代价是额外开辟了一个哈希表空间复杂度从O(1)升为O(n)。这就是所谓的“空间换时间”——用额外的内存开销换取大幅度的耗时下降。在实际面试中如果没有特别说明不允许使用额外空间一遍哈希表就是这道题的最优解。但请注意“平均”这个词哈希表在最坏情况下哈希冲突极其严重时查询复杂度可能退化为O(n)不过在 Java 的HashMap和 Python 的dict中都使用了成熟的扰动函数和扩容策略来压低冲突概率实际使用时完全不用担心这种极端情况。4. 哈希表选型解析为什么是 HashMap 而不是数组题目拿到手很多熟悉数据结构的人自然会想到哈希表。但哈希表也分好多实现形态Java 里有HashMap、Hashtable、HashSet这些都能用吗如果面试官要求不能使用语言内置的哈希结构你能不能自己手搓一个这些细节才是拉开差距的地方。4.1 HashMap、HashSet 与数组的性能对比先明确一点Java 的HashSet底层就是HashMap只不过它只关心键不关心值。本题需要返回下标所以必须用HashMap来同时记录值和下标HashSet只能告诉你“这个数存不存在”却不能告诉你“它在哪里”。如果数据范围很小且已知比如元素的值都在0到1000之间可以用一个定长数组模拟哈希表值作为数组下标索引作为数组值。理论上这种方式查询更快因为数组访问是真正的O(1)——连哈希函数都不用算了。但本题没有给出数值范围限制数组值可能是负数也可能非常大直接使用数组会浪费大量空间甚至出现下标越界。所以HashMap是更通用、更稳妥的选择。另外提一个容易被忽略的点HashMap允许null键和null值。如果数组中有null或者在某种变体题目中需要处理nullHashMap都能正常操作。而Hashtable不支持null这一点在选型时要注意。4.2 不用哈希函数行不行聊聊二叉搜索树方案有一种可能被追问的思路如果不想用哈希表还可以用二叉搜索树或者排序的方式。二叉搜索树方案的核心是依然遍历数组但用一棵二叉搜索树来存已经访问过的元素。每次查找补数时在树里做一次搜索时间复杂度为O(log n)。整体时间复杂度变为O(n log n)比哈希表的O(n)慢但好处是在最坏情况下依然是O(n log n)不会像哈希表那样退化。排序方案是另一个方向先给数组排序然后用双指针从两端向中间夹逼。但这里有个致命的问题——排序会打乱元素和原始下标的对应关系。你需要额外保存原始下标这会使代码复杂度上升不少。而且这种情况下你不能再直接返回原始的下标了必须先找到对应的原位置。这个思路在变式题里有价值但在本题中反而绕了远路。我会在下一节详细展开这个方案。4.3 手写哈希表面试官的经典进阶问题有些面试官会追问“如果现在不允许你使用现成的 HashMap你会怎么实现”这个问题考察的是对哈希表底层原理的真正理解。一个最简单的实现思路是链地址法class MyHashMap { private static final int SIZE 10007; private Entry[] buckets new Entry[SIZE]; private static class Entry { int key; int value; Entry next; Entry(int key, int value) { this.key key; this.value value; } } private int hash(int key) { return (key % SIZE SIZE) % SIZE; } public void put(int key, int val) { int index hash(key); Entry head buckets[index]; while (head ! null) { if (head.key key) { head.value val; return; } head head.next; } Entry entry new Entry(key, val); entry.next buckets[index]; buckets[index] entry; } public int get(int key) { int index hash(key); Entry head buckets[index]; while (head ! null) { if (head.key key) { return head.value; } head head.next; } return -1; } public boolean containsKey(int key) { return get(key) ! -1; } }这里选择SIZE 10007是因为它是一个质数稍微大于 10000能让元素在桶中分布得更均匀。这个方法配合题目使用完全足够了。当然面试时口头解释清楚底层原理比完整写出代码更常见但你能写出来一定会是加分项。5. 进阶变式当两数之和不再简单两数之和作为基础题真正好玩的地方在于它的各种变形。我从实际刷题和面试经历中整理了几个高频变式如果你已经顺利解决了经典版不妨挑战一下下面这些场景。5.1 设计一个两数之和类题目变成设计一个类支持add和find两种操作。add向数据结构中添加一个数find判断是否存在两个数之和等于给定值。这种场景下你需要考虑查询频率和插入频率谁更高。如果add次数远多于find你可以选择在每次find时才构建哈希索引避免频繁插入带来的开销如果反过来find多而add少则应该维护一个Map数值, 出现次数每次find时直接查表。核心难点是处理重复元素如果add(3)调用了两次find(6)应该返回true因为存在两个3可以相加。这时需要记录每个值出现的次数并在查询时判断补数是否等于当前数——如果是则必须要求当前值出现次数大于等于 2。5.2 返回所有不重复的组合而不是一组下标还有一种变式是“返回数组中和为 target 的所有数对且不允许重复”。这里不能直接套用一边哈希的写法因为你需要收集所有结果并且要去重。常见做法是先排序再用双指针或哈希表配合集合去重。排序双指针的思路是先排序然后左指针指向当前元素的下一个位置右指针指向数组末尾。如果两数之和小于target左指针右移如果大于target右指针左移如果等于target记录结果并同时移动两个指针跳过重复值。整体时间复杂度O(n log n)比单纯哈希表多了一个排序的耗时但换来了有序性和去重的便利。5.3 三数之和与四数之和三数之和是两数之和的直接延伸固定第一个数剩余部分转化为两数之和问题。但这里要注意去重操作固定第一个数时跳过重复值内部双指针找到两个数后也要跳过重复值。四数之和依此类推本质上都是固定的排序加双指针套路。我把这几个变式整理成了一张速查表方便你在复习时快速回忆变式解法核心时间复杂度注意点两数之和经典一遍哈希表O(n)先查后存两数之和设计类哈希表计数O(1) add / O(n) find注意重复元素次数两数之和返回所有组合排序 双指针O(n log n)去重三数之和排序 双指针O(n^2)固定一个数去重四数之和排序 双指针O(n^3)固定两个数去重5.4 有序数组版本双指针的正确打开方式刚才提到排序加双指针但要注意如果题目直接给的就是有序数组那么这几乎是最优解。因为有序数组可以直接利用单调性左指针指向数组头部右指针指向数组尾部。计算两数之和如果大于target说明需要更小的数右指针左移如果小于target说明需要更大的数左指针右移。直到两指针相遇。这个思路的时间复杂度是O(n)空间复杂度O(1)比哈希表方案更省内存。我遇到过有人拿这个解法去回答无序数组版本的两数之和说自己先排序再用双指针结果排序把下标打乱了导致无法返回原始下标——这个问题非常经典谨记区分“原数组无序”和“有序数组”这两种不同的题目设定。6. 常见问题与排查技巧实录6.1 我被面试官追问最多的三个问题第一个问题为什么 Java 的HashMap平均复杂度是O(1)这个问题需要从哈希函数的散列性质来回答但只要提到“均匀分布”和“负载因子”基本就能过关。第二个问题数组里如果有负数怎么办实际上负数完全不影响哈希表解法因为补数的计算就是简单的减法target - (-1)就等于target 1逻辑上依然成立。第三个问题如果有多个答案怎么办经典版题目假设只有一个答案但实际变式题中可能需要你返回所有答案这需要修改算法保证在找到一个答案后不立刻返回而是继续遍历。6.2 易错点自查清单结合我带过的学员和自己在刷题时踩过的坑我总结出以下高频错误内层循环从 0 而不是 i1 开始这样会让同一个元素被使用两次也可能导致同一对数被重复比较白白浪费时间。先 put 当前元素再查询补数在数组存在相同值元素时返回了错误结果比如[3, 3]中target 6可能返回[0, 0]或者[1, 1]。两遍哈希忘记判断下标不相等数组[3]target 6时错误返回[0, 0]。返回下标时顺序写反虽然某些在线判题系统允许任意顺序但有些系统严格要求先写位置靠前的下标为了保险起见还是养成正确顺序的习惯。记错变量名乍一看这不是算法问题但实际编码中这类低级错误浪费的时间往往比算法思路出错还多。6.3 一道题的三次提交记录我的优化轨迹我第一次刷这道题大约是在四年前当时的代码是暴力解法提交之后看到耗时排在倒数位置也没觉得有什么问题。后来有一次面试被追问“能不能更快”我当场没答上来回去老老实实把哈希表解法写了一遍才算真正吃透这道题。再后来看官方题解学到一遍哈希的写法忽然意识到代码简洁本身就是一种优化。同一道题三次提交代表了我对算法理解深度的三次跃升。从“能跑就行”到“考虑复杂度”再到“在正确的前提下追求简洁”这个过程几乎可以复用到任何一道算法题上。所以在刷这类型题目时我建议你不要只看一种做法就收工。每道题至少尝试写出暴力解和最优解两种版本并想清楚它们的复杂度差异。如果题目允许再想一想能不能用不同的数据结构实现——比如把哈希表换成树或者排序数组。这样一道题收获的就不只是一个答案而是一整套解题思路。6.4 给刷题新手的一个实用建议每年都有新人问我同一个问题刷题到底怎么刷才有效针对两数之和这道题我的回答是第一遍看题目后独立思考 5 分钟能写多少写多少写不出来直接看题解也没关系但一定要在 24 小时内独立重新写一遍。第二遍关上所有资料用最优解法从零开始写写完后对照代码检查顺序和边界条件。第三遍尝试讲解给一个完全不懂的人听。如果你能清楚地讲明白“为什么先查再存”和“为什么哈希表能把时间复杂度从 O(n^2) 降到 O(n)”这道题才算真正消化吸收。这个方法看着简单但能坚持下来的人不多。而且说句实在话两数之和所处的“哈希表家族”是整个算法面试里性价比最高的知识点之一——从两数之和出发你可以延伸到三数之和、四数之和、连续子数组之和等一系列相关题目。把这一道题啃透相当于打通了整个“子数组和目标值”的题型脉络。最后再分享一个我今天才用到的小技巧。在实际编码环境中如果你不确定哈希表的键值该放什么先想一个问题“我要查什么”本题中我们要查的是“某个数之前是否出现过”所以键是数字值是下标。一旦把“查询目标”想清楚数据结构的键值方向就不会搞反。这个思路我用在很多哈希表题目上成功率极高。
1. 题目拆解为什么这道题被称作“梦开始的地方”两数之和——LeetCode题库的第1题无数人刷题生涯的第一道坎。我在带新人入门算法时几乎每次都会从这道题开始讲起。原因很简单它足够简单以至于能让你快速建立信心但它又足够深刻背后藏着哈希表、时间复杂度分析、空间换时间这些贯穿整个算法学习的关键思路。更现实的一点是这道题在面试中的出场率高得离谱尤其是针对校招和初级岗位。题目本身非常直白给定一个整数数组nums和一个整数目标值target请你在该数组中找出和为目标值的那两个整数并返回它们的数组下标。你可以假设每种输入只会对应一个答案但是数组中同一个元素不能使用两遍。换成人话就是有一串数字你告诉我一个目标值我去这串数字里找两个数让它们加起来正好等于目标值然后把这两个数在数组中的位置告诉你。这里有两个容易被忽略的约束条件需要仔细揣摩。第一“只有一个答案”意味着这道题不需要处理多个解的情况你找到一对儿就能收工这大大简化了实现逻辑。第二“同一个元素不能使用两遍”这句话看起来是废话但它其实是在防止一种低级错误比如target 6数组是[3, 3]你不能说“我用下标0的那个3加上下标0的那个3等于6”因为这是同一个元素被用了两遍正确结果应该是[0, 1]。在真正动手写代码之前我想先聊一聊这道题的核心难点。这道题作为第1题天然带着“新手劝退”和“老手回味”的双重属性。新手容易一头扎进暴力解法里觉得能跑就行而老手看到这道题想的却是如何在各种变体中快速定位最优解。它的核心难点不是“怎么找到答案”而是“怎么更快地找到答案”——这里就涉及到了算法学习中最基本也最重要的一组概念时间复杂度和空间复杂度。2. 从暴力解法说起为什么能用但不宜多用2.1 暴力枚举的基本逻辑最朴素的想法是什么两层循环。外层循环固定第一个数内层循环遍历它后面的所有数逐一检查两个数的和是否等于target。这是一个零思考成本的思路几乎不需要任何数据结构知识只要会写for循环就能实现。public int[] twoSum(int[] nums, int target) { for (int i 0; i nums.length; i) { for (int j i 1; j nums.length; j) { if (nums[j] target - nums[i]) { return new int[] { i, j }; } } } return new int[] {}; }注意内层循环从i 1开始而不是从0开始。这既避免了i和j指向同一个元素的情况也避免了两层循环找到同一对数字的重复劳动。比如数组[2, 7, 11, 15]i 0时检查2 7等到i 1时就没必要再去检查7 2了因为它们在数学上是同一对组合。2.2 时间复杂度推演当数据量变大之后暴力解法的时间复杂度怎么算外层循环要跑n次n是数组长度内层循环平均跑n/2次总的比较次数大约是n * n / 2用大O符号表示就是O(n^2)。这意味着什么我用一组具体数字来展示假设数组长度n 1000暴力解法大约需要做 50 万次比较当n 10000时这个数字变成了 5000 万当n 100000时是 50 亿次。而哈希表解法在同样规模下只需要做大约n次操作也就是 10 万次左右。差距就在这里体现出来了——从 50 亿到 10 万跨越了五个数量级。我在实际开发中遇到过一个真实的类似场景不是算法题而是一个用户标签匹配功能。两个用户集合做两两匹配当时直接写了双重循环上线后数据量一上来接口响应直接飙到 8 秒后来改造成哈希索引才压到 200 毫秒以内。这类问题在 LeetCode 上叫“两数之和”在真实业务中叫“双层循环性能瓶颈”本质上是一回事。当然暴力解法也不是一无是处。它的空间复杂度是O(1)也就是除了输入的数组本身不需要额外的内存空间。当数据量很小比如n 100的时候暴力解法和哈希表解法的实际执行时间差距几乎可以忽略不计但代码却简单得多。所以我说“能用但不宜多用”——在算法题里你需要展示自己的思考深度在实际代码中你需要考虑后续的数据增长趋势两者都指向同一个结论暴力解法只适合作为理解题意的起步不适合作为最终答案。3. 哈希表解法空间换时间的最经典实践3.1 核心思路用“补数”代替“求和”暴力解法慢就慢在每次都要遍历整个数组去寻找搭档。那我们换个思路能不能把遍历过的元素记录下来下次直接查询这里引入一个“补数”的概念。对于数组中的每个元素nums[i]如果它真的存在于一个有效解中那么它的搭档必然是target - nums[i]。所以我们不需要在每一轮都做两层循环而是只需要做一件事检查target - nums[i]之前有没有出现过。这个思路的第一步是建立一张哈希表键Key存数组元素的值值Value存这个元素在数组中的下标。然后从头遍历数组对于当前元素先在哈希表里查一下target - nums[i]是否存在如果存在说明之前遍历过的某个元素和当前元素正好凑成目标值直接返回两个下标。如果不存在把当前元素的值和下标放进哈希表然后继续遍历下一个元素。这个过程中有一个非常关键的顺序问题必须“先查询再插入”。我强调这一点是因为很多初学者在这里栽过跟头。如果先把当前元素放入哈希表再查询补数那么当数组中出现两个相同值的元素时就可能查询到当前元素自身。举例来说nums [3, 2, 4]target 6如果先把3放进去再查询查到target - 3 3存在就会错误地返回[0, 0]而不是正确答案[1, 2]。3.2 两遍哈希 vs 一遍哈希到底差在哪哈希表解法又细分为两遍哈希和一遍哈希两种写法。两遍哈希的意思是第一遍遍历整个数组把所有元素都放入哈希表第二遍再遍历数组逐个查找补数。这种写法逻辑上更直观也更容易想到但存在一个隐藏的坑——重复元素处理。比如nums [3, 3]target 6。第一遍构建哈希表时因为键不能重复后一个3会覆盖前一个3的下标哈希表最终存的是{3: 1}。第二遍遍历时i 0查到target - 3 3在哈希表中对应下标是1返回[0, 1]结果正确。但这里需要额外加一个判断查到的下标不能和当前下标相同。比如nums [3]target 6第一遍建表存下{3: 0}第二遍i 0时查到下标0如果不加判断就会错误返回[0, 0]。一遍哈希则直接在遍历过程中边查边存。这种方式更优雅因为它在查找的同时完成了建表平均情况下遍历到一半左右就能找到答案而且天然规避了“同一下标匹配自身”的问题——因为当前元素还没有被放进表中查到的补数必然是之前已经遍历过的元素而不是当前元素。两遍哈希的代码长这样public int[] twoSum(int[] nums, int target) { MapInteger, Integer map new HashMap(); for (int i 0; i nums.length; i) { map.put(nums[i], i); } for (int i 0; i nums.length; i) { int complement target - nums[i]; if (map.containsKey(complement) map.get(complement) ! i) { return new int[] { i, map.get(complement) }; } } return new int[] {}; }一遍哈希的代码更简洁public int[] twoSum(int[] nums, int target) { MapInteger, Integer map new HashMap(); for (int i 0; i nums.length; i) { int complement target - nums[i]; if (map.containsKey(complement)) { return new int[] { map.get(complement), i }; } map.put(nums[i], i); } return new int[] {}; }注意一遍哈希返回时先返回map.get(complement)再返回i因为查到的那个元素在数组中更靠前。这个顺序不能写反否则虽然不影响“找对了一对数”这个事实但会影响下标的排列是否符合题目要求。我见过不少人在这个细节上被测试用例卡住。3.3 复杂度量化分析这里我直接给出一组复杂度对比数据方便你直观理解差异解法时间复杂度空间复杂度适合场景暴力枚举O(n^2)O(1)数组极小n 100两遍哈希表O(n)O(n)思路演示、教学场景一遍哈希表O(n)O(n)面试与竞赛首选哈希表在查询上的平均时间复杂度是O(1)这让整体算法从嵌套循环降级为单层循环时间复杂度从O(n^2)降为O(n)。代价是额外开辟了一个哈希表空间复杂度从O(1)升为O(n)。这就是所谓的“空间换时间”——用额外的内存开销换取大幅度的耗时下降。在实际面试中如果没有特别说明不允许使用额外空间一遍哈希表就是这道题的最优解。但请注意“平均”这个词哈希表在最坏情况下哈希冲突极其严重时查询复杂度可能退化为O(n)不过在 Java 的HashMap和 Python 的dict中都使用了成熟的扰动函数和扩容策略来压低冲突概率实际使用时完全不用担心这种极端情况。4. 哈希表选型解析为什么是 HashMap 而不是数组题目拿到手很多熟悉数据结构的人自然会想到哈希表。但哈希表也分好多实现形态Java 里有HashMap、Hashtable、HashSet这些都能用吗如果面试官要求不能使用语言内置的哈希结构你能不能自己手搓一个这些细节才是拉开差距的地方。4.1 HashMap、HashSet 与数组的性能对比先明确一点Java 的HashSet底层就是HashMap只不过它只关心键不关心值。本题需要返回下标所以必须用HashMap来同时记录值和下标HashSet只能告诉你“这个数存不存在”却不能告诉你“它在哪里”。如果数据范围很小且已知比如元素的值都在0到1000之间可以用一个定长数组模拟哈希表值作为数组下标索引作为数组值。理论上这种方式查询更快因为数组访问是真正的O(1)——连哈希函数都不用算了。但本题没有给出数值范围限制数组值可能是负数也可能非常大直接使用数组会浪费大量空间甚至出现下标越界。所以HashMap是更通用、更稳妥的选择。另外提一个容易被忽略的点HashMap允许null键和null值。如果数组中有null或者在某种变体题目中需要处理nullHashMap都能正常操作。而Hashtable不支持null这一点在选型时要注意。4.2 不用哈希函数行不行聊聊二叉搜索树方案有一种可能被追问的思路如果不想用哈希表还可以用二叉搜索树或者排序的方式。二叉搜索树方案的核心是依然遍历数组但用一棵二叉搜索树来存已经访问过的元素。每次查找补数时在树里做一次搜索时间复杂度为O(log n)。整体时间复杂度变为O(n log n)比哈希表的O(n)慢但好处是在最坏情况下依然是O(n log n)不会像哈希表那样退化。排序方案是另一个方向先给数组排序然后用双指针从两端向中间夹逼。但这里有个致命的问题——排序会打乱元素和原始下标的对应关系。你需要额外保存原始下标这会使代码复杂度上升不少。而且这种情况下你不能再直接返回原始的下标了必须先找到对应的原位置。这个思路在变式题里有价值但在本题中反而绕了远路。我会在下一节详细展开这个方案。4.3 手写哈希表面试官的经典进阶问题有些面试官会追问“如果现在不允许你使用现成的 HashMap你会怎么实现”这个问题考察的是对哈希表底层原理的真正理解。一个最简单的实现思路是链地址法class MyHashMap { private static final int SIZE 10007; private Entry[] buckets new Entry[SIZE]; private static class Entry { int key; int value; Entry next; Entry(int key, int value) { this.key key; this.value value; } } private int hash(int key) { return (key % SIZE SIZE) % SIZE; } public void put(int key, int val) { int index hash(key); Entry head buckets[index]; while (head ! null) { if (head.key key) { head.value val; return; } head head.next; } Entry entry new Entry(key, val); entry.next buckets[index]; buckets[index] entry; } public int get(int key) { int index hash(key); Entry head buckets[index]; while (head ! null) { if (head.key key) { return head.value; } head head.next; } return -1; } public boolean containsKey(int key) { return get(key) ! -1; } }这里选择SIZE 10007是因为它是一个质数稍微大于 10000能让元素在桶中分布得更均匀。这个方法配合题目使用完全足够了。当然面试时口头解释清楚底层原理比完整写出代码更常见但你能写出来一定会是加分项。5. 进阶变式当两数之和不再简单两数之和作为基础题真正好玩的地方在于它的各种变形。我从实际刷题和面试经历中整理了几个高频变式如果你已经顺利解决了经典版不妨挑战一下下面这些场景。5.1 设计一个两数之和类题目变成设计一个类支持add和find两种操作。add向数据结构中添加一个数find判断是否存在两个数之和等于给定值。这种场景下你需要考虑查询频率和插入频率谁更高。如果add次数远多于find你可以选择在每次find时才构建哈希索引避免频繁插入带来的开销如果反过来find多而add少则应该维护一个Map数值, 出现次数每次find时直接查表。核心难点是处理重复元素如果add(3)调用了两次find(6)应该返回true因为存在两个3可以相加。这时需要记录每个值出现的次数并在查询时判断补数是否等于当前数——如果是则必须要求当前值出现次数大于等于 2。5.2 返回所有不重复的组合而不是一组下标还有一种变式是“返回数组中和为 target 的所有数对且不允许重复”。这里不能直接套用一边哈希的写法因为你需要收集所有结果并且要去重。常见做法是先排序再用双指针或哈希表配合集合去重。排序双指针的思路是先排序然后左指针指向当前元素的下一个位置右指针指向数组末尾。如果两数之和小于target左指针右移如果大于target右指针左移如果等于target记录结果并同时移动两个指针跳过重复值。整体时间复杂度O(n log n)比单纯哈希表多了一个排序的耗时但换来了有序性和去重的便利。5.3 三数之和与四数之和三数之和是两数之和的直接延伸固定第一个数剩余部分转化为两数之和问题。但这里要注意去重操作固定第一个数时跳过重复值内部双指针找到两个数后也要跳过重复值。四数之和依此类推本质上都是固定的排序加双指针套路。我把这几个变式整理成了一张速查表方便你在复习时快速回忆变式解法核心时间复杂度注意点两数之和经典一遍哈希表O(n)先查后存两数之和设计类哈希表计数O(1) add / O(n) find注意重复元素次数两数之和返回所有组合排序 双指针O(n log n)去重三数之和排序 双指针O(n^2)固定一个数去重四数之和排序 双指针O(n^3)固定两个数去重5.4 有序数组版本双指针的正确打开方式刚才提到排序加双指针但要注意如果题目直接给的就是有序数组那么这几乎是最优解。因为有序数组可以直接利用单调性左指针指向数组头部右指针指向数组尾部。计算两数之和如果大于target说明需要更小的数右指针左移如果小于target说明需要更大的数左指针右移。直到两指针相遇。这个思路的时间复杂度是O(n)空间复杂度O(1)比哈希表方案更省内存。我遇到过有人拿这个解法去回答无序数组版本的两数之和说自己先排序再用双指针结果排序把下标打乱了导致无法返回原始下标——这个问题非常经典谨记区分“原数组无序”和“有序数组”这两种不同的题目设定。6. 常见问题与排查技巧实录6.1 我被面试官追问最多的三个问题第一个问题为什么 Java 的HashMap平均复杂度是O(1)这个问题需要从哈希函数的散列性质来回答但只要提到“均匀分布”和“负载因子”基本就能过关。第二个问题数组里如果有负数怎么办实际上负数完全不影响哈希表解法因为补数的计算就是简单的减法target - (-1)就等于target 1逻辑上依然成立。第三个问题如果有多个答案怎么办经典版题目假设只有一个答案但实际变式题中可能需要你返回所有答案这需要修改算法保证在找到一个答案后不立刻返回而是继续遍历。6.2 易错点自查清单结合我带过的学员和自己在刷题时踩过的坑我总结出以下高频错误内层循环从 0 而不是 i1 开始这样会让同一个元素被使用两次也可能导致同一对数被重复比较白白浪费时间。先 put 当前元素再查询补数在数组存在相同值元素时返回了错误结果比如[3, 3]中target 6可能返回[0, 0]或者[1, 1]。两遍哈希忘记判断下标不相等数组[3]target 6时错误返回[0, 0]。返回下标时顺序写反虽然某些在线判题系统允许任意顺序但有些系统严格要求先写位置靠前的下标为了保险起见还是养成正确顺序的习惯。记错变量名乍一看这不是算法问题但实际编码中这类低级错误浪费的时间往往比算法思路出错还多。6.3 一道题的三次提交记录我的优化轨迹我第一次刷这道题大约是在四年前当时的代码是暴力解法提交之后看到耗时排在倒数位置也没觉得有什么问题。后来有一次面试被追问“能不能更快”我当场没答上来回去老老实实把哈希表解法写了一遍才算真正吃透这道题。再后来看官方题解学到一遍哈希的写法忽然意识到代码简洁本身就是一种优化。同一道题三次提交代表了我对算法理解深度的三次跃升。从“能跑就行”到“考虑复杂度”再到“在正确的前提下追求简洁”这个过程几乎可以复用到任何一道算法题上。所以在刷这类型题目时我建议你不要只看一种做法就收工。每道题至少尝试写出暴力解和最优解两种版本并想清楚它们的复杂度差异。如果题目允许再想一想能不能用不同的数据结构实现——比如把哈希表换成树或者排序数组。这样一道题收获的就不只是一个答案而是一整套解题思路。6.4 给刷题新手的一个实用建议每年都有新人问我同一个问题刷题到底怎么刷才有效针对两数之和这道题我的回答是第一遍看题目后独立思考 5 分钟能写多少写多少写不出来直接看题解也没关系但一定要在 24 小时内独立重新写一遍。第二遍关上所有资料用最优解法从零开始写写完后对照代码检查顺序和边界条件。第三遍尝试讲解给一个完全不懂的人听。如果你能清楚地讲明白“为什么先查再存”和“为什么哈希表能把时间复杂度从 O(n^2) 降到 O(n)”这道题才算真正消化吸收。这个方法看着简单但能坚持下来的人不多。而且说句实在话两数之和所处的“哈希表家族”是整个算法面试里性价比最高的知识点之一——从两数之和出发你可以延伸到三数之和、四数之和、连续子数组之和等一系列相关题目。把这一道题啃透相当于打通了整个“子数组和目标值”的题型脉络。最后再分享一个我今天才用到的小技巧。在实际编码环境中如果你不确定哈希表的键值该放什么先想一个问题“我要查什么”本题中我们要查的是“某个数之前是否出现过”所以键是数字值是下标。一旦把“查询目标”想清楚数据结构的键值方向就不会搞反。这个思路我用在很多哈希表题目上成功率极高。
