mobile wallpaper 1mobile wallpaper 2mobile wallpaper 3mobile wallpaper 4
1885 words
5 minutes
算法入门(二):哈希表与两数之和
2026-10-21

给你一组数字 [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。

当前下标当前数字需要的数字查询已有记录接下来做什么
045表为空,没有 5保存 4 → 0
118没有 8保存 1 → 1
263没有 3保存 6 → 2
336找到 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.java
java 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

提示:每读到一个数字,就检查它是否已经出现;发现重复便结束。写完后,应能说明为什么它通常只需要一次遍历,以及额外空间保存了什么。

下一篇会遇到另一种重复工作:每次重新计算一段连续数据的总和。我们将用双指针与滑动窗口让区间逐步移动,并复用已经得到的计算结果。

Share

If this article helped you, please share it with others!

算法入门(二):哈希表与两数之和
https://mizuki.mysqil.com/posts/algorithm-02-hash-table/
Author
梦幻晨风
Published at
2026-10-21
License
CC BY-NC-SA 4.0

Some information may be outdated

Table of Contents