给你一组数字 [2, 7, 11, 15],要找出两个位置,让对应数字相加等于 9。答案是下标 [0, 1],因为 2 + 7 = 9。
这个问题用两层循环很容易写出来。但如果数组很长,我们能不能减少重复查找?这一篇就从这个小问题出发,学习哈希表怎样把“找过的东西”记录下来。
阅读前只需要会数组、循环和方法调用。代码使用 Java 17+;如果还不熟悉复杂度,可以先读第一篇与系列目录。
一、先把题目说完整
我们约定:输入一个整数数组 values 和目标值 target,返回任意一对不同下标,使对应元素的数学和等于目标值。如果不存在,返回空数组。
数组可以包含负数、零和重复数字。例如 [3, 3] 的两个元素虽然数值相同,却位于不同位置,因此目标为 6 时可以返回 [0, 1]。对于只有一个元素的 [3],不能把它使用两次。
这里求的是一对下标,不需要列出所有组合,也不要求返回下标最小的那一对。这些要求会影响后面的实现,不能在写完代码后才补充。
| 输入 | 目标 | 合法结果 | 原因 |
|---|---|---|---|
[2, 7, 11, 15] | 9 | [0, 1] | 两个不同位置的和为 9 |
[3, 3] | 6 | [0, 1] | 重复数字可以来自不同位置 |
[3] | 6 | [] | 不能重复使用同一个位置 |
[-2, 5, 0] | 3 | [0, 1] | 负数也参与正常计算 |
[] | 9 | [] | 没有可选元素 |
二、最直接的办法:把所有数对试一遍
先固定第一个位置 i,再让 j 从它后面逐个尝试:
// 核心循环片段,放在接收 values 和 target 的方法中。for (int i = 0; i < values.length; i++) { for (int j = i + 1; j < values.length; j++) { if ((long) values[i] + values[j] == target) { return new int[] {i, j}; } }}return new int[0];j 从 i + 1 开始,既保证两个位置不同,也避免把同一个数对正反检查两遍。
如果有 n 个元素,又一直没找到答案,需要检查的数对数量为:
(n - 1) + (n - 2) + ... + 1 = n(n - 1) / 2忽略常数和低阶项,最坏时间复杂度是 O(n²)。输入扩大到原来的十倍,比较次数可能接近原来的百倍。它只使用几个变量,额外空间是 O(1)。
这份简单实现很有价值:容易理解,也能作为之后验证更快算法的参照。
三、把“找另一个数”变成一次查询
假设当前读到 7,目标是 9,我们真正需要知道的是:
前面有没有出现过 9 - 7,也就是 2?如果每次都重新扫描前面的数组,仍会反复做相同的查找。可以维护一张表,记录已经遇到的数字,以及它所在的下标。
在 Java 中,Map 表示键与值的映射。这里选择 HashMap 实现它:
Map<Long, Integer> seen = new HashMap<>();键是已经出现的数字,值是它的下标。put 保存一条映射,get 按键寻找对应值。哈希表会根据键计算位置,再检查键是否匹配,通常可以快速定位。
不同键可能计算到相同位置,这叫哈希冲突。因此,哈希表查询通常按平均或期望 O(1) 理解,不能把所有输入下的查找都承诺为恒定时间。本篇使用普通整数键,主要关注如何减少重复扫描,不展开内部冲突处理。
四、手动走一遍“先查,再存”
换一个稍长的过程:数组 [4, 1, 6, 3],目标为 9。
| 当前下标 | 当前数字 | 需要的数字 | 查询已有记录 | 接下来做什么 |
|---|---|---|---|---|
| 0 | 4 | 5 | 表为空,没有 5 | 保存 4 → 0 |
| 1 | 1 | 8 | 没有 8 | 保存 1 → 1 |
| 2 | 6 | 3 | 没有 3 | 保存 6 → 2 |
| 3 | 3 | 6 | 找到 6 → 2 | 返回 [2, 3] |
这里有一个始终成立的规则:检查下标 i 时,表里只记录此前的位置。 因此,只要找到需要的数字,它的下标一定小于 i,不会重复使用当前位置。
如果先存再查,在 [3]、目标 6 的情况下,就会先保存 3 → 0,接着找到自己,错误地返回 [0, 0]。
对于 [3, 3] 则不同。处理第一个 3 时查不到,保存它;处理第二个 3 时找到的是第一个位置,结果合法。
五、Java 实现
下面是完整核心方法,省略了类声明和导入;需要导入 java.util.Map、java.util.HashMap。带 main 的文件可以直接下载:HashTwoSum.java,也可以下载系列全部源码。
public static int[] twoSum(int[] values, int target) { if (values == null) { throw new IllegalArgumentException("values must not be null"); } Map<Long, Integer> seen = new HashMap<>(); for (int i = 0; i < values.length; i++) { long needed = (long) target - values[i]; Integer previous = seen.get(needed); if (previous != null) { return new int[] {previous, i}; } seen.put((long) values[i], i); } return new int[0];}空数组和单元素数组自然返回 [];null 则被视为无效输入。我们没有向表中存放 null 值,所以这里 get 返回 null 就表示没有找到键。
如果同一个数字再次出现,put 会覆盖之前的下标。这不影响“找到任意一对”的要求,因为保留下来的仍然是此前出现过的一个位置。若题目要求所有数对,映射内容和返回结果都需要重新设计。
为什么补数使用 long
Java 的 int 有取值范围,减法也可能溢出。比如目标为 -2,数组是两个 2147483647:它们的数学和显然不是 -2,但使用 int 相加会溢出成 -2。
所以比较时要先扩大计算范围。代码中的 (long) target - values[i] 会先把目标转换成 long,再进行减法;表中的键也使用 Long。不能写成 (long) (target - values[i]),因为括号里的 int 减法已经先算完了。
运行与观察
把下载文件保存为 HashTwoSum.java,在文件所在目录运行:
javac -encoding UTF-8 HashTwoSum.javajava HashTwoSum预期输出:
[0, 1][0, 1][]三行分别验证普通输入、重复数字和不存在答案的情况。可以修改 main 中的数组,再重新编译运行。
六、复杂度怎样变化
数组最多遍历一次,每次执行一次查询和至多一次插入。在哈希操作平均或期望为常数时间的前提下,总时间是 O(n)。
表里最多保存 n 个不同数字,所以额外空间是 O(n)。它通过保存历史信息减少查找工作,这是常见的时间与空间取舍。
| 方法 | 最坏或期望时间口径 | 额外空间 | 核心工作 |
|---|---|---|---|
| 两层枚举 | 最坏 O(n²) | O(1) | 检查每个数对 |
| 哈希表 | 平均或期望 O(n) | O(n) | 查询此前是否出现补数 |
数组很小时,实际耗时还会受对象分配、装箱等因素影响。复杂度用于判断规模增长趋势,并不代表所有小输入下哈希表都更快。
七、自己改一道题
把需求改成:判断数组是否存在重复数字,只返回 true 或 false。
先写两层循环,再思考历史记录还需要保存下标吗?如果只关心“出现过没有”,可以使用 HashSet<Integer>。
至少检查下面四组输入:
[1, 2, 3, 1] → true[1, 2, 3] → false[0, 0] → true[] → false提示:每读到一个数字,就检查它是否已经出现;发现重复便结束。写完后,应能说明为什么它通常只需要一次遍历,以及额外空间保存了什么。
下一篇会遇到另一种重复工作:每次重新计算一段连续数据的总和。我们将用双指针与滑动窗口让区间逐步移动,并复用已经得到的计算结果。
If this article helped you, please share it with others!
Some information may be outdated






