两数之和Java解法：从暴力到哈希表O(n)优化与面试要点

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从i+1走到尾，每一对都检查一次。

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) { Map<Integer, 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 = 3，map.containsKey(3)为 true，map.get(3) = 1，1 != 0，所以返回[0, 1]，结果正确。

但如果数组只有一个 3，比如nums = [3]，target = 6，map里存的是{3: 0}。循环时i = 0，complement = 3，map.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) { Map<Integer, 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 = 0：complement = 3，map 为空，不包含 3，把3 -> 0存进去。
• i = 1：complement = 3，map 里有3 -> 0，返回[0, 1]。

再试nums = [2, 7]，target = 9：

• i = 0：complement = 7，map 为空，存2 -> 0。
• i = 1：complement = 2，map 里有2 -> 0，返回[0, 1]。

一遍哈希表的时间复杂度同样是 O(n)，空间复杂度 O(n)，但代码更简洁，循环次数少了一半，在面试中也更好讲清楚。我个人的建议是：面试时直接写一遍哈希版本，并且主动解释为什么不需要下标相等判断，这会给面试官留下“真的理解，而不是背答案”的好印象。

3.3 两个版本的复杂度对比

为了更直观，我把两种解法和暴力解法放在一起对比：

从时间复杂度看，哈希表相比暴力是降维打击，但代价是额外的 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 刷这道题，最常见的报错无非这几种，我挨个说一下排查思路：

其中“答案包含同一个元素”这个坑出现频率最高。拿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 的题目，每一道都值得“三刷”。第一刷求过，第二刷求懂，第三刷求讲。尤其是这种面试高频题，能做到不看题解，在白纸上从暴力解到最优解一步一步写出来，并且把每一步的复杂度变化说清楚，面试基本就稳了。

最后一句话给大家：两数之和只是开始，但它教会你的“空间换时间，哈希帮你找”这句话，会在后面几十道题里反复回响。把这道题吃透，比囫囵吞枣刷完十道题都值。