很多人打开力扣 hot100第一眼看到的就是「两数之和」。我见过不少同学觉得这题太简单扫一眼就关了也见过更多人背下了哈希表的答案却讲不出为什么这么写。这道题在力扣 hot100 里的位置太特殊了——它几乎是所有 Java 面试者刷题之路的第一站也是很多面试官三分钟热身时最常用的题。但恰恰是这道看起来最简单的题最能暴露一个人的基本功HashMap 用的熟不熟、复杂度会不会算、边界情况想不想得全、代码风格干不干净。这篇文章我想认真聊聊两数之和这道题尤其是 Java 版本的完整解法。不会只丢一个最优解代码就完事而是从暴力解开始推演一步步走到哈希表方案再把里面容易踩的坑、面试官的追问、以及从这道题延伸出去的一类题都梳理清楚。无论你是刚准备刷题的新手还是想把 hot100 吃透的求职者这篇都值得你花十分钟读完。1. 题目到底在考什么先看懂两数之和的本质1.1 把题目翻译成人话原题描述很简洁给定一个整数数组nums和一个整数目标值target请你在该数组中找出和为目标值的那两个整数并返回它们的数组下标。你可以假设每种输入只会对应一个答案并且你不能使用两次相同的元素。这几句话里有几个关键约束必须读出来。第一返回的是下标不是值本身这意味着解题时得跟着下标走。第二每种输入只会有一个答案所以不需要处理多解的情况找到一个就可以返回。第三同一个元素不能用两次这个约束在实现时常常被忽略后面我会专门讲它是怎么坑人的。1.2 从生活场景理解「查找配对」问题我习惯把这题理解成在书店里找两本书。假设书架上每本书都有自己的编号你要找两本编号加起来恰好等于某个数字的书。最笨的办法就是拿起第一本然后挨个往后翻其他书看编号能不能凑上翻完一轮没找到再拿起第二本再从头翻一遍。这就是暴力解。那聪明一点的做法是什么你一边翻书一边在手上的小本子上记录书编号是多少放在第几个位置。之后每翻到一本新书你只需要查一下小本子上有没有一本书编号等于目标值减去当前这本的编号。有的话直接去对应位置拿书没有的话就把当前这本登记进小本子继续翻下一本。这个小本子在程序里就是哈希表。1.3 为什么 hot100 把它放在第一题力扣 hot100 是从海量题目里筛出来的高频面试题集合覆盖了大多数面试常考的算法和数据结构。两数之和作为整个列表的第一题并不是因为它难而是因为它是非常好的「数据结构入门题」。它用最小的代码量完整展示了从 O(n^2) 到 O(n) 的优化过程涉及了哈希表这个面试最高频的数据结构还天然能延伸出双指针、排序、去重等一系列后续考点。算是用最简单的外壳装了最核心的面试知识点。2. 暴力解为什么能过但千万别止步于「能过」2.1 两层循环的朴素写法先看大部分人第一直觉写出来的代码public int[] twoSum(int[] nums, int target) { int n nums.length; for (int i 0; i n; i) { for (int j i 1; j n; j) { if (nums[i] nums[j] target) { return new int[]{i, j}; } } } return new int[0]; }这段代码在力扣上是能通过的因为题目给的数据范围不大O(n^2) 的复杂度在 n 只有几百、几千的时候完全跑得动。我见过很多初学者刷到这里就觉得自己搞定了这恰恰是最危险的错觉。2.2 暴力解的复杂度到底有多高来分析一下这段代码的时间复杂度。外层循环跑 n 次内层循环平均跑 n/2 次总的比较次数是 n*(n-1)/2量级就是 O(n^2)。空间复杂度是 O(1)除了几个临时变量没有额外开销。O(n^2) 在数据量小的时候感觉不出来但你把 n 从 1000 提到 100000计算量就差了大约一百倍。真实的工程场景里接口请求动辄几万几十万的数据量没人能接受这种复杂度。面试官让你写两数之和最终想看到的一定是 O(n) 的解法。2.3 暴力解真正的学习价值暴力解不是没有价值它的价值在于帮你建立「基线」。我们分析一个算法题第一步永远是先想最暴力的做法确认它能解决这个问题再去优化。暴力解提供了一个正确性基准后面你写了任何优化版本都可以拿它来验证结果对不对。另外暴力解里有个细节值得提一下内层循环从j i 1开始而不是从 0 开始。这样既避免了同一个元素自己和自己的组合也避免了一对元素被重复计算两次。这个写代码的直觉后续做很多数组问题都用得上。3. 哈希表解法从「找人」到「登记簿」的思路转换3.1 核心推理把查找从 O(n) 降到 O(1)暴力解慢在哪里慢在每次都要扫描整个数组去找target - nums[i]是否存在的这个过程。数组是一个无序的存储结构查找一个元素只能逐个遍历这就是 O(n) 的来源。有没有一种数据结构能让我以 O(1) 的代价查到一个元素是否存在并且拿到它的下标有就是哈希表。Java 里对应的是HashMap。哈希表内部通过哈希函数把 key 映射到数组桶位上所以查找的平均时间复杂度是 O(1)。于是思路就变成了遍历数组的过程中维护一个 HashMapkey 存「已经出现过的元素值」value 存「这个元素的下标」。每次遇到一个新元素nums[i]先查一下target - nums[i]是不是已经在 map 里了。如果在那答案就找到了如果不在把当前元素放进去继续遍历。3.2 为什么一定是 HashMap 而不是 HashSet很多新手会混淆这两个结构。HashSet 只能判断「某个值是否存在」但它拿不到下标。而这题要返回的是下标所以必须有 value 来存下标信息。HashMap 的 key 存值、value 存下标完美匹配需求。这里有一个值得记住的做题思维题目要求返回什么数据结构就存什么。返回下标就存下标返回所有组合就把组合存成 List返回数量就直接计数。先明确输出再设计存储。3.3 为什么必须边遍历边放而不能先全部放进去这是整道题里最容易踩的坑我面试别人的时候也常用这个点来区分候选人是不是真的理解了哈希表解法。错误写法是这样的先遍历一遍数组把所有元素放进 map再遍历一遍检查target - nums[i]是否在 map 里。看起来没毛病但碰到重复元素就出问题了。比如nums [3, 3]target 6。如果你先把所有元素放进去map 中 key3 的 value 会被第二次放入的 3 覆盖成下标 1。然后遍历第一个下标 0 时查target - nums[0] 3发现 map 里有返回[0, 1]——看起来碰巧对了。但如果题目稍微改一下比如nums [3, 3]但你遍历到下标 1 才去查就会返回[1, 1]这就不对了因为同一个元素不能被用两次。边遍历边放就天然规避了这个问题。因为当你站在下标 i 时map 里只存了下标 0 到 i-1 的元素永远不会用当前这个元素匹配自己。正确的核心逻辑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); }4. Java 实现的细节打磨一份能拿高分的完整答案4.1 完整参考代码带注释与边界处理一个能拿高分的解答不只是把核心逻辑写出来还要有清晰的命名、合理的边界处理、和良好的代码习惯。我一般会这样写public int[] twoSum(int[] nums, int target) { // 边界情况数组为空或长度小于2直接返回空数组 if (nums null || nums.length 2) { return new int[0]; } // key为数组元素值value为元素下标 MapInteger, Integer numIndexMap new HashMap(); for (int i 0; i nums.length; i) { int complement target - nums[i]; // 已经遍历过的部分中是否存在需要的差值 if (numIndexMap.containsKey(complement)) { return new int[]{numIndexMap.get(complement), i}; } // 不存在则记录当前值的位置继续遍历 numIndexMap.put(nums[i], i); } // 按题设不会走到这一步但保留兜底返回 return new int[0]; }这段代码的时间复杂度为 O(n)因为一次遍历每次 map 操作平均 O(1)空间复杂度为 O(n)因为最坏情况下需要把 n 个元素都放进 map。这个 trade-off 在面试时要主动讲清楚用 O(n) 的空间换来了 O(n) 的时间。4.2 从暴力到哈希代码是怎么一步步演化的我建议初学者在草稿纸上先写出暴力解确认正确性然后思考这样一个问题暴力解里最耗时的部分是什么是内层循环的查找。能不能让查找更快如果能用一个 map 把所有见过的值存下来每次直接查是不是就不需要那个内层循环了带着这个思路去写优化版逻辑是水到渠成的。不要一上来就背哈希表的答案。你自己推一遍暴力到哈希的演化过程面试官问「为什么用哈希表」的时候你才能从原理上讲清楚而不是只能说「大家都这么写」。4.3 易错点对照这几处写错的人最多我整理了几个 Java 实现里常见的容易写错的地方对照如下易错点错误示例正确做法原因数组空指针直接访问 nums.length先判 null 再取 length工程习惯防止 NPE返回空数组return nullreturn new int[0]返回空数组比 null 更安全元素自己匹配自己先全部放入 map 再查边查边放避免同一元素被使用两次重复 key 覆盖使用 put 多次导致 value 被覆盖先 containsKey 再决定是否放入保证存的是最早出现的下标返回顺序不统一有时先 i 后 map有时反过来统一先 map 下标再当前下标保持代码稳定可读4.4 关于 getOrDefault 的一段补充有些同学会看到getOrDefault的写法觉得更简洁。比如Integer preIndex map.getOrDefault(target - nums[i], -1); if (preIndex ! -1) { return new int[]{preIndex, i}; }这种写法功能上没问题但有一个隐患如果数组中存在下标为 -1 的合法情况数组下标确实是非负的所以实际不会语义上就不干净。更重要的是当差值不存在时返回 -1你还得区分「不存在」和「下标真的为 0」这两种情况。虽然在这道题里用 -1 作为哨兵是安全的但从代码可读性角度我更推荐containsKeyget的显式写法让人一眼看懂逻辑。5. 面试官常在两数之和后面埋的追问5.1 如果数组是有序的能不能优化空间这道题最常见的变体是给定一个升序排列的数组找出两个数使它们的和等于 target返回它们的下标。数组有序时可以用双指针对撞法。一个指针指向数组头部一个指向尾部计算两数之和。和太大了右指针左移和太小了左指针右移找到相等就返回。这个过程的时间复杂度是 O(n)空间复杂度 O(1)比哈希表更省空间。但要注意原题的两数之和返回的是原始下标如果你先对数组排序下标就乱了。所以面试里遇到「有序数组 返回下标」的组合需要先把原数组转成一个包含值和原始下标的 Pair 数组排序时带着下标一起走再用双指针。如果只要求返回值那直接对原数组排序加双指针就行。5.2 如果要求返回所有不重复的解而不是一个解这个变体直接通向三数之和、四数之和。典型的做法是先排序然后固定一个数剩下的部分用双指针找两数之和同时跳过重复元素避免产生重复解。// 伪代码思路排序后固定 i双指针找两数 Arrays.sort(nums); for (int i 0; i n - 2; i) { if (i 0 nums[i] nums[i - 1]) continue; int left i 1, right n - 1; while (left right) { int sum nums[i] nums[left] nums[right]; if (sum target) { // 记录结果然后去重移动双指针 } else if (sum target) { left; } else { right--; } } }5.3 如果数组非常大内存装不下哈希表怎么办这是一个典型的工程扩展问题。这时候要考虑的不是单机内存解法而是能否把问题拆到多台机器并行处理或者利用外部排序后分段处理甚至如果数据分布有规律可以先判断 target 的范围缩小候选数据。这类问题没有标准答案面试官考察的是你有没有处理大数据的意识。5.4 两数之和是 nSum 问题的地基两数之和最简单的版本其实是 value 版本给定数组和一个 target判断是否存在两个数的和等于 target。在此基础上可以一步步升级两数之和返回下标需要用 HashMap 存值到下标的映射两数之和返回所有不重复的值组合排序加双指针去重三数之和固定一个数转化为两数之和四数之和固定两个数再转化为两数之和把这个链条理解透比单独背十道题有用得多。hot100 里面很大一部分题目都是这种层层递进的关系抓住主线学习效率会高很多。6. 刷 hot100 的正确节奏从一道题到一类题6.1 一道两数之和能带出哪些知识点我自己刷题有个习惯每道题做完之后不只记答案而是列一下这道题关联的知识点清单。两数之和的知识点清单大致是这样的数据结构HashMap 的查、插、覆盖行为算法复杂度时间复杂度和空间复杂度的 trade-off双指针思想有序数组的 O(1) 空间解法排序与下标保持Pair 排序、自定义比较器去重技巧排序后跳过相邻重复元素边界处理空数组、单元素数组、无解情况每一个知识点都可以继续展开。比如 HashMap 的 put 方法的返回值、containsKey 的时间复杂度、扩容机制这些都是 Java 面试八股文里很常见的内容。刷题和八股文不是对立的你完全可以在做这道题的时候顺手把这些都复习了。6.2 我的刷题笔记模板我建议你给每道 hot100 题目建一个笔记包含四个部分题目一句话描述用自己的话说清楚题目要求暴力解思路与复杂度先写最朴素的想法再分析慢在哪最优解思路与复杂度记录优化过程而不是只写最终答案易错点与延伸题把踩过的坑、面试官的追问写下来两数之和的笔记里我会特别标注这次学到的核心经验数组查找慢用哈希表换时间返回什么就存什么边遍历边维护哈希表可以避免同一个元素用两次。6.3 给刚开始刷 hot100 的人一个建议hot100 不是用来背的是用来建立算法思维的。前期不要追求每天刷很多题我反而建议一天只做一两道但每道都把它吃透暴力解推导一遍最优解推到一遍网上找一两篇题解看看思路有什么不同再把相关变体题做一遍。这个过程比机械刷十道题有用得多。两数之和作为第一题价值就在于此。它用最简单的方式让你体验了完整的刷题方法论理解问题、暴力基线、结构优化、代码实现、边界处理、变体延伸。把这套方法论掌握住后面的 99 道题会顺畅很多。我个人刷这道题已经不下十遍了每次面试前还会翻出来看一眼。不是因为我记不住答案而是每次看都能用不同的视角去审视它的边界去联想新的题目。刷题这事的核心不在数量而在于你能否把一道经典题背后承载的思维方式真正变成自己的东西。希望这篇两数之和的完整梳理能帮你走好 hot100 的第一步。
