LeetCode Hot 100 · 哈希篇
哈希（HashMap / HashSet）在算法面试里的核心价值只有一句话：把「查找是否存在 / 出现了多少次」从 O(n) 降到 O(1)。Hot 100 里哈希分类的三道题，恰好对应三种经典用法——「查补数」「造 key 分组」「去重 + 判存在」。本篇按「面试手撕」的标准重写，每道题都给出暴力解 → 最优解 → 复杂度逐步推导 → CodeTop 真实变体。
1. 两数之和
题意
给定整数数组 nums 和目标值 target，找出和为 target 的两个整数的下标（每种输入只有一个答案，同一个元素不能重复使用）。
输入：nums = [2,7,11,15], target = 9
输出：[0,1] // nums[0] + nums[1] == 9难点与易错点
- 返回的是下标，不是值。所以 HashMap 的 value 必须存下标（
HashMap<Integer, Integer>），不能只存布尔值标记「存在」。这是新手最容易犯的错：光判断存在了，结果拿不出下标。 - 同一个元素不能用两次。典型坑：
nums = [3,2,4], target = 6。如果「先存后查」，遍历到 3 时 map 里已有3→0，会误判3+3=6返回[0,0]。正确做法是先查后存——查补数时当前元素还没进 map，天然避开了自己配自己。 - 边界：题目保证只有一个答案，所以
return new int[]{}只是编译占位，永远不会执行；但面试时最好写出来，说明你考虑了「无解」分支。
题目本质：单次遍历 + O(1) 查询补数。对每个数 x，判断 target - x 是否已经出现在之前遍历过的元素里。
现实类比：超市收银员找补。你知道总价，手里拿着一张钱，想知道之前是否有人递过正好能凑整的另一张钱。每扫一件商品就把它登记在账本里，扫下一件时先翻账本查「有没有那张补数的钱」。
容器选择：需要 O(1) 判断某个值（补数）是否存在 → HashMap；同时要返回下标 → value 存下标。
解法一：暴力 / 直观
双重循环枚举所有数对 (i, j)，判断 nums[i] + nums[j] == target。
class Solution {
public int[] twoSum(int[] nums, int target) {
int n = nums.length;
// 外层枚举第一个数
for (int i = 0; i < n; i++) {
// 内层从 i+1 开始，避免同一元素用两次、避免重复枚举 (i,j) 和 (j,i)
for (int j = i + 1; j < n; j++) {
if (nums[i] + nums[j] == target) {
return new int[]{i, j};
}
}
}
return new int[]{}; // 题目保证有解，此处仅为编译占位
}
}复杂度逐步推导：外层循环跑 n 次，内层对每个 i 跑 n - i - 1 次，总比较次数为 (n-1) + (n-2) + ... + 1 = n(n-1)/2，所以时间复杂度 O(n²)；只用了常数个临时变量，空间 O(1)。
瓶颈在哪：每一轮内层循环都在做同一件事——「在剩余元素里找一个值等于 target - nums[i]」。这个「找」是线性扫描，是 O(n²) 的根源。如果能把这个「找」变成 O(1)，整体就降下来了。
解法二：优化 / 最优（哈希表）
边遍历边把元素存入 HashMap，每到一个新元素先查「补数是否已存在」。
class Solution {
public int[] twoSum(int[] nums, int target) {
// key: 元素值，value: 元素下标
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int complement = target - nums[i];
// 先查询：补数是否已经存在于 map 中
// 注意必须先查后存，防止使用同一元素两次
if (map.containsKey(complement)) {
return new int[]{map.get(complement), i};
}
// 后存入：将当前值及其下标记录，供后续元素查询
map.put(nums[i], i);
}
return new int[]{};
}
}复杂度逐步推导：
- 外层循环遍历数组一遍，共 n 次迭代；
- 每次迭代里
map.containsKey与map.put都是 HashMap 的均摊 O(1) 操作； - 所以总时间 = 外层 O(n) × 内层哈希查询 O(1) = O(n)。
- 空间：最坏情况下（答案在最后才凑齐）map 要存下前面 n-1 个元素，占 O(n)。
为何「先查后存」能一步到位：暴力法里两个下标有先后关系（i < j），哈希法复用了这个顺序——遍历到 nums[j] 时，nums[i]（i < j）已经全部进 map，补数 target - nums[j] 若存在，必然对应一个 i < j，直接返回即正确且无重复使用。
💭 思考：两数之和为什么想到用哈希，以及为什么「先查后存」？——暴力版的内层循环每一轮都在做同一件事：「在剩余元素里线性找一个值等于
target - nums[i]」，这个 O(n) 的「找」就是 O(n²) 的根源。哈希表恰好把「找是否存在」压到 O(1)，于是整体塌缩到 O(n)。至于顺序：因为要求「同一个元素不能用两次」，先查后存让当前元素还没进 map，天然避开了「自己配自己」的坑（反例[3,2,4]配 6）。看到「两数之和 / 找补数 / 判断是否存在」这类信号，第一反应就是「用哈希把查找降成 O(1)」。
多解法对比
| 解法 | 时间复杂度 | 空间复杂度 | 适用场景 |
|---|---|---|---|
| 暴力双重循环 | O(n²) | O(1) | 数据量极小，或内存极度受限 |
| 哈希表一次遍历 | O(n) | O(n) | 本题标准解，任何规模都适用 |
本题约束下 n 可能到 10⁴，O(n²) 约 10⁸ 次比较，勉强但危险；而 O(n) 哈希解只需 10⁴ 次查询，且实现短、不容易出 bug，是面试必须给出的版本。空间换时间是本题的核心权衡。
CodeTop 变体
- 字节 / 腾讯高频延伸：
15. 三数之和——固定一个数后，把问题降维成「两数之和」，再用双指针去重；18. 四数之和同理套娃。 - 有序数组变体：
167. 两数之和 II - 输入有序数组——数组已排序，改用双指针对撞，空间降为 O(1)。 - 哈希法追问：
454. 四数相加 II——四个数组各取一个数和为 0，把前两个数组的和存哈希、后两个查补数，O(n²)。 - 数据结构变体：
653. 两数之和 IV - 输入 BST——中序 + 双指针，或边遍历边查 HashSet。 - 真实追问话术：面试官常问「如果要求返回所有满足条件的下标对，怎么改？」——此时 map 的 value 要改成
List<Integer>（存多个下标），查到补数后枚举所有配对；「如果数组有序且要求 O(1) 空间？」——双指针。
49. 字母异位词分组
题意
给定字符串数组，把字母组成相同、顺序不同的词（字母异位词）分到同一组，按任意顺序返回所有分组。
输入：strs = ["eat","tea","tan","ate","nat","bat"]
输出：[["bat"],["nat","tan"],["ate","eat","tea"]]难点与易错点
- 如何造出「唯一标识字母构成」的 key。字母异位词本质是「每种字符出现次数相同」，需要一种方法把
eat、tea、ate归到同一个 key。排序是最直观的：三者排序后都是aet。 - Java 排序字符串的写法：
String不能直接 sort，必须str.toCharArray()→Arrays.sort(chars)→new String(chars)。漏掉toCharArray转数组这步是常见报错。 - 返回值的构造：直接
map.values()返回的是Collection，LeetCode 要求List<List<String>>，需new ArrayList<>(map.values())包装；顺序可以任意，不要纠结排序。 - 边界：空字符串
""也是合法输入，排序后仍是""，单独成组；不要把它当成非法输入跳过。
题目本质：一个分组问题——找到一个能唯一标识「字母构成」的 key，把同 key 的字符串归为一组。
现实类比：图书馆整理书籍。不同书名但内容相同（字母相同）的书要放在同一格。给每本书的「字母排序后的书名」作为货架编号，同编号的书放一起。
容器选择：HashMap<String, List<String>>，key 是排序后的规范形式，value 是同组原始字符串列表；需要按 key 快速查找/插入 → HashMap。
解法一：暴力 / 直观（排序作 key）
对每个字符串排序得到规范 key，computeIfAbsent 按 key 分组。
class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
// key: 排序后的字符串（异位词的唯一标识）
// value: 同属一组的原始字符串列表
Map<String, List<String>> map = new HashMap<>();
for (String str : strs) {
// 字符串 → 字符数组 → 排序 → 转回字符串，得到规范化 key
char[] chars = str.toCharArray();
Arrays.sort(chars);
String key = new String(chars);
// key 不存在时自动创建空列表，再追加原始字符串
map.computeIfAbsent(key, k -> new ArrayList<>()).add(str);
}
// 返回 map 中所有 value 组成的列表
return new ArrayList<>(map.values());
}
}复杂度逐步推导：设数组有 n 个字符串，最长长度为 k。
- 外层遍历 n 个字符串；
- 每个字符串要排序，长度为 k 的字符串排序是 O(k log k)；
- 所以总时间 = 外层 O(n) × 单串排序 O(k log k) = O(n·k·log k)。
- 空间：map 最终存下所有 n 个字符串（含 key 的拷贝），总量约 O(n·k)。
瓶颈在哪：时间主要耗在「每个字符串都要排序」。当字符串很长时，k log k 会拖慢整体；如果字符串只含小写字母（长度有限但 n 巨大），排序其实做了多余工作——因为字母构成只跟「每个字符出现几次」有关，跟顺序无关。
解法二：优化（字符计数作 key，O(n·k)）
用「26 个字母的出现次数」构造 key，避免排序。字符集固定为小写字母时，这是更优解。
class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
// key: 由 26 个字母出现次数拼接成的字符串（如 "1#0#0#..."），唯一标识字母构成
// value: 同组原始字符串列表
Map<String, List<String>> map = new HashMap<>();
for (String str : strs) {
int[] count = new int[26];
// 统计每个小写字母出现的次数
for (char c : str.toCharArray()) {
count[c - 'a']++;
}
// 用 StringBuilder 拼接计数，作为 key（用 # 分隔防止 1+11 与 11+1 混淆）
StringBuilder sb = new StringBuilder();
for (int i = 0; i < 26; i++) {
sb.append(count[i]).append('#');
}
String key = sb.toString();
map.computeIfAbsent(key, k -> new ArrayList<>()).add(str);
}
return new ArrayList<>(map.values());
}
}复杂度逐步推导：
- 外层遍历 n 个字符串；
- 每个字符串遍历一遍统计字符是 O(k)，再拼固定 26 位 key 是 O(26)（常数）；
- 所以总时间 = 外层 O(n) × 内层 O(k) = O(n·k)，与 k log k 相比，当 k 较大时明显更快；
- 空间仍为 O(n·k)（map 存所有字符串 + 计数 key）。
💭 思考：排序作 key 已经能 O(n·k·log k)，为什么还要「字符计数作 key」？——瓶颈在排序：每个字符串都
Arrays.sort一次，多花了log k因子。而字母异位词的本质是「每种字符出现次数相同」，跟顺序无关，排序其实做了多余工作。既然字符集固定为 26 个小写字母，直接用int[26]计数、拼成"1#0#0#..."这样的 key，就把每个字符串的处理从O(k log k)压到O(k)。看到「分组 + 唯一标识某个特征」的信号，先想「排序作 key 图省事」，再问一句「特征是否只跟计数有关」——是的话换计数 key，这是纯时间优化。
多解法对比
| 解法 | 时间复杂度 | 空间复杂度 | 适用场景 |
|---|---|---|---|
| 排序作 key | O(n·k·log k) | O(n·k) | 字符集不限（大小写、Unicode 都行），实现最直观 |
| 字符计数作 key | O(n·k) | O(n·k) | 字符集固定（如小写字母），字符串较长时更快 |
本题约束只保证小写字母，理论上计数法更优；但面试手撕时，排序法代码最短、最不易错，先给出排序法并主动说出「若字符串很长可换计数法优化到 O(n·k)」，是展示深度和取舍的最佳方式。
CodeTop 变体
- 字节 / 阿里高频关联：
242. 有效的字母异位词——判断两个字符串是否互为异位词，本质就是「比较两个计数数组」或「排序后比较」。 - 滑动窗口套娃：
438. 找到字符串中所有字母异位词、567. 字符串的排列——固定窗口内用 26 位计数数组匹配，是本题「计数作 key」思想在窗口上的延续。 - 真实追问话术：面试官常问「字符串很长（k 很大），怎么优化？」——答案即上面的计数法 O(n·k)；再追问「字符集很大（不限于 26 个字母）怎么办？」——用质数乘积或直接排序作 key。
128. 最长连续序列
题意
给定未排序整数数组，找出数字连续的最长序列长度，要求时间复杂度 O(n)。
输入：nums = [100,4,200,1,3,2]
输出：4
解释：最长连续序列是 [1,2,3,4]，长度为 4难点与易错点
- 「要求 O(n)」直接否决了排序。最直观的思路是「排序后扫描连续段」，但排序至少 O(n log n)，不满足硬性约束，必须想别的办法。
- 朴素哈希会退化到 O(n²)。如果把每个数都当成起点，对每个起点
while向后延伸（如[1,2,3,...,n]里每个数都往后数一遍），总复杂度是 O(n²)。关键技巧：只从「序列起点」开始延伸——所谓起点，是「x-1 不存在」的数。这样每个元素最多被数到一次。 - 先 Set 去重再遍历：重复元素（如
[1,2,2,3]）若不先去重，会影响长度统计和「是否存在 x-1」的判断，用 HashSet 天然解决。 - 长度计算：内层 while 结束时
y是「第一个不在序列里的数」，序列长度 =y - x，不要写成y - x + 1。
题目本质：以每个「序列起点」出发向后延伸。用 HashSet 去重后，只从序列第一个元素（不存在 x-1 的元素）开始计数，避免重复计算。
现实类比：找车队。一条公路上有很多车，每辆车编号连续。你只从「领头车」（前面没有车的那辆）开始数，数到队伍断开为止，记录最长的那支队伍。
容器选择：需要 O(1) 判断某数是否存在 → HashSet；不需要记录下标或频次 → 不需要 HashMap。
解法一：暴力 / 直观（排序）
先排序，再线性扫描连续段。
class Solution {
public int longestConsecutive(int[] nums) {
if (nums.length == 0) return 0;
Arrays.sort(nums); // O(n log n)
int maxLen = 1;
int curLen = 1;
for (int i = 1; i < nums.length; i++) {
if (nums[i] == nums[i - 1]) {
// 跳过重复元素，不断开也不增长
continue;
} else if (nums[i] == nums[i - 1] + 1) {
// 连续，长度 +1
curLen++;
maxLen = Math.max(maxLen, curLen);
} else {
// 断开，重新计数
curLen = 1;
}
}
return maxLen;
}
}复杂度逐步推导：排序是 O(n log n)，后续扫描一遍 O(n)，总时间复杂度 O(n log n)；空间取决于排序实现（Java 对 int 用双轴快排，原地，O(log n) 栈空间）。
瓶颈在哪：排序把「找连续」变成了简单的扫描，但排序本身 O(n log n) 已经超了题目 O(n) 的硬性要求，这一版在面试里只能作为「先说个直觉解」的铺垫。
解法二：优化 / 最优（HashSet + 只从起点延伸）
全部入 Set 去重，遍历时只从「x-1 不存在」的起点向后延伸。
class Solution {
public int longestConsecutive(int[] nums) {
// 将所有数字放入 HashSet，O(1) 查询是否存在
Set<Integer> numSet = new HashSet<>();
for (int num : nums) {
numSet.add(num);
}
int maxLen = 0;
for (int x : numSet) {
// 只从序列起点开始遍历：x-1 不存在，说明 x 是某段连续序列的起点
// 跳过非起点，避免 O(n²) 的重复计算
if (numSet.contains(x - 1)) {
continue;
}
// 从起点 x 向后延伸，统计序列长度
int y = x + 1;
while (numSet.contains(y)) {
y++;
}
// y - x 即为本段序列的长度
maxLen = Math.max(maxLen, y - x);
}
return maxLen;
}
}复杂度逐步推导（这是本题面试必问，务必讲清「为什么是 O(n) 而不是 O(n²)」）：
- 第一步：把 n 个数加入 HashSet，每个 O(1)，合计 O(n)；
- 第二步：遍历 set 里的每个元素
x（至多 n 个，去重后可能更少），外循环 O(n) 次迭代； - 关键在内层 while：表面看 while 可能 O(n)，但整体不是 n × n。因为「只有
x-1不存在时」才会进入 while，也就是说每个数字 y 最多在某个起点的 while 里被contains查询一次——一旦 y 是序列中间元素，它一定满足y-1存在，会在外循环里被continue跳过，不会自己再启动一次 while； - 所以所有 while 的
contains调用次数加起来 不超过 n 次，每次 O(1)； - 总时间 = 外循环 O(n) + 所有 while 合计 O(n) = O(n)；
- 空间：HashSet 存储全部 n 个元素，O(n)。
💭 思考：为什么这题必须绕开排序，而「只从起点延伸」为什么能保住 O(n)？——看到「要求 O(n)」这个硬约束，排序 O(n log n) 直接出局，只能靠 O(1) 查询的 HashSet。朴素想法是「每个数都当起点往后数」，但
[1,2,3,...,n]里每个数都往后数一遍会退化成 O(n²)。关键观察：一个连续序列里，只有「x-1不存在」的那个数才是真正的起点，其余数都会被外循环的continue跳过，每个元素最多被某个起点的 while 查询一次。所以「去重 + 只从起点延伸」才是这题从 O(n²) 塌缩到 O(n) 的灵魂。看到「连续序列 + O(n)」这个组合，就该想到「Set 判存在 + 只从起点数」。
多解法对比
| 解法 | 时间复杂度 | 空间复杂度 | 适用场景 |
|---|---|---|---|
| 排序 + 扫描 | O(n log n) | O(log n)（或 O(1) 若原地） | 不要求 O(n) 时最简单 |
| HashSet + 起点延伸 | O(n) | O(n) | 本题标准解，满足 O(n) 硬约束 |
本题明确要求 O(n)，排序法直接出局。哈希法用 O(n) 空间换 O(n) 时间，且「只从起点延伸」这个去重剪枝是本题的灵魂——面试官就是要看你能不能讲清「为什么 while 不会退化成 O(n²)」。
CodeTop 变体
- 字节 / 腾讯高频关联：
674. 最长连续递增序列——数组有序（按下标连续）的弱化版，直接一次扫描即可；300. 最长递增子序列——注意是「子序列」不是「连续」，用 DP + 二分，与本题解法完全不同，面试常拿来对比区分。 - 并查集思路：
128也可以用 Union-Find 解（相邻数合并），字节一面偶尔会追问「除了 Set，还有什么数据结构能 O(n)？」——答并查集，能体现知识广度。 - 真实追问话术：面试官常问「如果要返回这个最长序列本身，怎么改？」——把
maxLen = Math.max(...)换成同时记录当前起点与长度，最后从bestStart依次 +1 拼出结果；「如果数据流式进来，怎么做？」——引出并查集或 TreeSet 动态维护。
小结：哈希三题覆盖了 HashMap/HashSet 的三种核心用法——「查补数」（两数之和）、「造 key 分组」（异位词分组）、「去重 + 判存在 + 剪枝」（最长连续序列）。把「查找」从 O(n) 压到 O(1)，就是这类题从暴力到最优的全部秘密。
章末提问
- 两数之和为什么必须「先查后存」，反过来会怎样？——结论：先存后查会把「自己配自己」误判成解。因为当前元素入 map 后，若
target - x == x（如[3,2,4]的 target=6），查到的补数下标就是它自己，返回[i,i]违反「同一个元素不能用两次」；先查后存则天然避开这个坑。 - 最长连续序列的内层 while 会不会退化成 O(n²)？为什么不会？——结论：不会，整体仍是 O(n)。因为只有「
x-1不存在」的起点才会进入 while，序列中间的元素都在外循环被continue跳过，每个元素最多被某个起点的 while 查询一次，所有 contains 调用合计不超过 n 次。 - 异位词分组既然有 O(n·k) 的计数法，为什么面试里更该先写 O(n·k·log k) 的排序法？——结论：排序法代码最短、最不易错，是「先写对」的首选。因为计数法只在字符集固定且字符串很长时才带来可观收益，而手撕里稳定正确比常数优化更值钱——先交排序法、再主动说出「可换计数法优化」，是展示取舍的正确姿势。