1. 题目解读为什么两数之和是Hot 100的门面力扣Hot 100是所有刷题人绕不开的一份清单而其中排在第一位的就是这道两数之和。作为一个常年拿Java刷题的开发者我可以说这道题的重要程度被严重低估了——它看着简单但真正能在面试中把这个题讲透的人并不多。先看题目本身给定一个整数数组nums和一个整数目标值target要求在数组里找出和为目标值的那两个整数并返回它们的数组下标。题目保证每种输入只会对应一个答案但是数组中同一个元素在答案里不能重复出现。这里有几个关键细节马虎不得返回的是下标不是值本身。很多人第一次敲的时候容易搞混return 出去的是[0, 1]而不是[2, 7]。“同一个元素不能重复使用”这句话有坑。比如nums [3,3]target 6答案是[0,1]不能因为 3 3 6 就直接拿i和i配对。题目保证有唯一解所以不用处理“找不到”的情况但代码里还是要有个默认返回否则编译不过。为什么这道题能排到Hot 100的第一位我的理解是它是哈希表优化查找这个核心思想的最佳入门题。暴力解是一眼能想到的但怎么优化到O(n)背后正是算法面试最常考的空间换时间策略。后面你会看到这道题的思路会反复出现在三数之和、四数之和、和为K的子数组等更难的题目里属于那种“学会一道撑起一片”的题。这篇博文适合这样几类人来看刚开始刷力扣、想从Hot 100入门的Java初学者准备Java后端面试需要在白板上快速写清楚这道题并能应对追问的人已经在刷题但只会背答案想知道每一步为什么这么写的人。2. 暴力穷举第一版代码与复杂度分析2.1 双层循环的直观解法拿到这道题最朴素的想法就是把所有两个数的组合都试一遍看哪一对加起来等于 target。用两个循环外层指针i从头走到尾内层指针j从i1走到尾每一对都检查一次。class Solution { 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]; } }这段代码里有一个细节内层循环的j为什么从i 1开始而不是从 0 开始这里其实做了两件事避免同一个元素和自己配对。如果j从 0 开始i 0, j 0时会把nums[0]用两次这违背了题目要求。去掉重复的组合。如果j也从 0 开始(i, j)和(j, i)会重复检查虽然不影响答案正确性但白白增加了一半的运算量。这种写法在数据量小的时候没毛病但它的性能瓶颈非常明显数组越长组合数越多。假设数组长度是 n两层循环一共要比较n*(n-1)/2次也就是时间复杂度是 O(n²)。空间上只用了一个int数组做返回值所以空间复杂度是 O(1)。2.2 为什么暴力解法不适合面试力扣的判题系统对这道题比较宽容哪怕你用暴力解法提交数据量不大的时候也能通过。但如果你在面试现场只写出这个版本面试官大概率会追问一句“还能不能更快”这个追问背后考察的是你对算法复杂度的敏感度。当n 10^5时n² 10^10哪怕计算机一秒钟能跑 10^8 次基础操作暴力解法也需要 100 秒才能出结果。而实际业务中数组规模到十万级是很常见的事所以暴力解法只能在思路上当垫脚石不能作为面试终稿。我第一次做这道题的时候就是先写了暴力版本然后卡在了“怎么去掉一层循环”上。后来才意识到问题的本质是对于每一个nums[i]我们都在剩余数组里“查找”有没有target - nums[i]这个值。查找一个值在不在集合里最优雅的数据结构就是哈希表。2.3 复杂度分析的直观理解可以用一个生活化的例子来辅助理解假设你在一个会议室里要找两个人他们的年龄加起来刚好是 100 岁。暴力解法是让第二个人从第一个人开始挨个问“你多大了咱俩加起来是不是100”每个人都要问一圈问的次数是所有人的两两组合数。那有没有更聪明的办法有。你可以准备一张登记表每进来一个人先查一下表上有没有人正好是“100 - 你的年龄”如果有恭喜找到了如果没有把你的年龄和名字写到表上。这样每个人只需要查表一次整体就变成了线性时间。这个“登记表”就是哈希表。3. 哈希表优化从 O(n²) 到 O(n) 的关键一步3.1 第一版哈希表两遍遍历哈希表的思路非常直接先用一次循环把数组里每个元素的值作为 key下标作为 value存进一个HashMap。然后再遍历一次数组对于每个nums[i]检查target - nums[i]是否在 map 里如果在就说明找到了另一半个答案。class Solution { 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[0]; } }这段代码里最关键的一行是map.get(complement) ! i。为什么需要这个判断因为题目不允许同一个元素用两次。考虑nums [3, 3]target 6的情况第一次循环结束后map 里存的是{3: 1}注意第二个 3 覆盖了第一个 3 的下标。第二次循环里i 0时complement 3map.containsKey(3)为 truemap.get(3) 11 ! 0所以返回[0, 1]结果正确。但如果数组只有一个 3比如nums [3]target 6map里存的是{3: 0}。循环时i 0complement 3map.containsKey(3)为 true但map.get(3) 0 i说明找到了它自己不符合要求跳过。循环结束返回空数组。两遍哈希表的时间复杂度是 O(n)因为两次循环都是线性遍历HashMap 的put和containsKey平均都是 O(1)。空间复杂度是 O(n)因为需要额外的 map 来存所有元素。3.2 进阶版本一遍哈希表两遍哈希已经很好了但有没有可能一遍循环就搞定想一下我们不一定要先把所有元素都存进 map 再回头找。可以在遍历的过程中边存边找。对于当前元素nums[i]我们先检查target - nums[i]是否已经在 map 里。如果在说明之前已经遍历过这个互补元素直接返回它的下标和当前下标。如果不在说明还没遇到过互补元素那就把当前元素存进 map继续往后走。class Solution { 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[0]; } }看到区别了吗一遍哈希版不再需要map.get(complement) ! i这个判断。为什么因为当前元素nums[i]是在containsKey检查之后才 put 进 map 的所以在检查的时候map 里存的都是下标小于 i 的元素根本不可能出现“map 里存的就是当前元素自己”这种情况。题目要求的一个元素只用一次在这个写法里天然满足。拿nums [3, 3]target 6来验证i 0complement 3map 为空不包含 3把3 - 0存进去。i 1complement 3map 里有3 - 0返回[0, 1]。再试nums [2, 7]target 9i 0complement 7map 为空存2 - 0。i 1complement 2map 里有2 - 0返回[0, 1]。一遍哈希表的时间复杂度同样是 O(n)空间复杂度 O(n)但代码更简洁循环次数少了一半在面试中也更好讲清楚。我个人的建议是面试时直接写一遍哈希版本并且主动解释为什么不需要下标相等判断这会给面试官留下“真的理解而不是背答案”的好印象。3.3 两个版本的复杂度对比为了更直观我把两种解法和暴力解法放在一起对比解法时间复杂度空间复杂度循环次数是否需要判断下标相等暴力双层循环O(n²)O(1)n*(n-1)/2内层从 i1 开始天然避免两遍哈希表O(n)O(n)2n需要map.get(complement) ! i一遍哈希表O(n)O(n)n不需要从时间复杂度看哈希表相比暴力是降维打击但代价是额外的 O(n) 空间。这就是典型的空间换时间——在绝大多数场景下O(n) 的额外空间是完全可以接受的尤其是当 n 只有几万到几十万的时候。注意HashMap 的containsKey和put操作平均时间复杂度是 O(1)。如果哈希冲突非常严重Java 8 之后 HashMap 会将链表转成红黑树最坏情况下退化到 O(log n)。但在算法题的数据规模下HashMap 的表现基本可以当作 O(1) 看待。4. 面试追问与常见陷阱4.1 面试官真正想考什么两数之和在面试中的出镜率高得离谱不只是因为它简单而是因为它能一次性考察多个基础能力读题能力能不能第一时间抓住“返回下标”“同一元素不能用两次”这两个关键约束。代码规范类的声明、方法签名、返回值对不对map 的泛型写没写全。复杂度意识能不能从暴力解 O(n²) 主动优化到 O(n)。解释能力为什么一遍哈希表可以不用检查下标相等这个问题能筛掉一大批背答案的人。我记得有一次模拟面试候选人三分钟就写出了哈希解但当我追问“如果数组中存在重复元素会怎样”时他愣住了。这不是他不懂哈希表而是他没理解哈希表的覆盖机制和它在这个题目里带来的影响。写代码只是表象理解每个细节背后的成因才是面试想考察的。4.2 数组无序时能不能用双指针这是一个高频追问答案是不能直接用。双指针的经典适用场景是有序数组。比如数组是[2, 7, 11, 15]target 9左右指针一夹逼就能找到。但题目给的数组是无序的如果先排序下标信息就丢了而我们返回的偏偏是下标。有人会说那我可以定义一个额外的类把值和原始下标一起存起来排序后再用双指针。比如class Node { int val; int index; Node(int val, int index) { this.val val; this.index index; } }然后对Node数组按值排序再用双指针找时间复杂度是 O(n log n)排序的复杂度空间复杂度 O(n)。但这比哈希表的 O(n) 要差而且代码复杂得多。所以在这个题目上哈希表是真正的正统解法双指针仅作为知识延伸存在。双指针真正的舞台是三数之和。下一小节我会讲到。4.3 HashMap 的 key 和 value 方向别搞反新手最常犯的一个错误是把数组下标当作 key把数组值当作 value 存进 map。如果这么存在查target - nums[i]时就无法根据差值直接定位到对应下标了因为 key 是下标而你需要的是根据值找下标。所以记住key 存数组元素的值value 存数组元素的下标只有这样才能实现“知道差值直接 index 找下标”的效果。还有一个小细节HashMap 的 key 不能存基本类型 int必须用包装类 Integer。Java 的自动装箱机制会在编译期帮你转换但这意味着 map 的查找会比较值而不是比较引用。所以map.containsKey(complement)判断的是数值相等不会有问题。但如果你直接调用map.get(complement)而没有先判空当 key 不存在时会返回 null再拿去和int比较就会触发空指针异常。所以我们总是先用containsKey判断或者用getOrDefault处理。5. 刷题实战从两数之和到后续算法题5.1 提交报错最常见的几种情况在力扣上用 Java 刷这道题最常见的报错无非这几种我挨个说一下排查思路现象原因解决方案编译错误类名不对力扣要求类名必须叫Solution方法签名和题目一致新建类时直接用题目给的默认类名返回了值而不是下标比如return new int[]{nums[i], nums[j]}改成return new int[]{i, j}答案包含同一个元素nums[3,3]时返回了[0,0]检查暴力解的内层循环起始值或哈希解中的下标相等判断提交超时用了 O(n²) 暴力解且测试数据量较大使用哈希表解法其中“答案包含同一个元素”这个坑出现频率最高。拿nums [3, 3]举例有些新手在两次循环时内层j从 0 开始导致i 0, j 0时就把两个下标都返回出去了。力扣的判题系统会直接报错因为[0, 0]虽然数值相加等于 6但下标相同违反了题目要求。5.2 用本地 IDE 调试的小技巧如果你在校验思路时不想反复提交到力扣可以在本地写一个main方法手动构造测试用例public class TwoSumTest { public static void main(String[] args) { Solution solution new Solution(); int[] nums1 {2, 7, 11, 15}; int[] result1 solution.twoSum(nums1, 9); System.out.println(Arrays.toString(result1)); int[] nums2 {3, 2, 4}; int[] result2 solution.twoSum(nums2, 6); System.out.println(Arrays.toString(result2)); int[] nums3 {3, 3}; int[] result3 solution.twoSum(nums3, 6); System.out.println(Arrays.toString(result3)); } }第二个测试用例很关键。nums [3, 2, 4]target 6如果只用循环检查“nums[i] nums[i]是否等于 target”会误以为3 3 6成立把[0, 0]返回出去。但正解是2 4 6返回[1, 2]。把这个用例放进本地测试能提前拦截这个错误。我自己写测试用例的习惯是除了题目给的示例再额外加两个边界场景。一是上面提到的重复元素场景二是只有一个元素的场景。这两类用例能覆盖绝大多数隐蔽 bug。5.3 这道题和后续题目的关联两数之和学完不要急着庆祝因为它的思想会被后续好几道题反复套用。**三数之和15题**是两数之和的直系升级版。要求找到所有和为 0 的三元组且不能重复。思路是先对数组排序然后固定一个数剩下两个数用双指针夹逼。这时候双指针就有用武之地了因为排序后数组是有序的。但注意三数之和不能用哈希表直接套因为要去重哈希表处理去重比较麻烦。**四数之和18题**是三数之和的再升级固定两个数剩下两个数用双指针。时间复杂度从 O(n²) 变成 O(n³) 的逻辑也很清晰。**和为 K 的子数组560题**则用到了哈希表加前缀和的组合思路遍历时记录前缀和并利用哈希表统计每个前缀和出现的次数。这个解法里“空间换时间”的味道更浓也是两数之和思路的延续。可以说两数之和是你建立算法自信心的第一站。它让你明白简单题不是不需要动脑而是让你在简单题里学会最重要的思维模型——用哈希表把查找从 O(n) 降到 O(1)。这个模型一旦建立后面很多看似复杂的题目底层思路都会清晰起来。5.4 我的一些实操心得这道题我前前后后刷过不下五遍每次都有新的感悟。第一次是懵懵懂懂看题解第二次是自己写出来但还是会漏掉下标相等判断第三次才真正理解一遍哈希表为什么不需要那个判断第四、五次已经能把它当作讲解模板讲给别人听。有一个感受想分享给正在刷题的朋友力扣 Hot 100 的题目每一道都值得“三刷”。第一刷求过第二刷求懂第三刷求讲。尤其是这种面试高频题能做到不看题解在白纸上从暴力解到最优解一步一步写出来并且把每一步的复杂度变化说清楚面试基本就稳了。最后一句话给大家两数之和只是开始但它教会你的“空间换时间哈希帮你找”这句话会在后面几十道题里反复回响。把这道题吃透比囫囵吞枣刷完十道题都值。