最近集中刷了一批 LeetCode 热门题其中凡是涉及 Hash 的题做完之后我都会单独停下来整理一遍思路。很多人一听到 Hash 这个词想到的可能是文件校验、前端打包文件名后面那串指纹或者终端里 md5sum 之类的命令但算法题里我们讨论的 Hash几乎都是哈希表HashMap / HashSet这套键值映射结构。它的核心能力说起来很朴素把一个目标对象映射成一个索引插入和查找的平均复杂度都做到 O(1)。也正是这一点让它在刷题场景里成了优化暴力枚举的头号工具。这篇笔记选了 LeetCode 上三道很有代表性的题来复盘第 1 题两数之和、第 49 题字母异位词分组、第 560 题和为 K 的子数组。三道题难度从 Easy 到 Medium正好把哈希表的三种典型用法都过了一遍查询补数、构造分组键、前缀和计数。如果你刚开始刷 LeetCode或者刷了一些题但总觉得 Hash 的题没有系统套路这篇记录应该能帮你把这些题背后的思考路径一次性理清楚。如果你只是好奇哈希表在算法里到底怎么用我不打算讲太多高深理论直接跟着三道题走一遍自然会明白。1. 为什么这三道题值得反复复盘1.1 算法里的 Hash 到底解决什么问题工程里 Hash 的特点是给一个对象计算出一个固定长度的指纹。算法里我们说的哈希表则更接近一个动态索引。你可以把数组理解成一种用整数当下标的映射而哈希表就是把下标扩展到了任意类型字符串、对象、甚至是数组本身。当我们想“根据某个属性快速找到另一个信息”时哈希表就是那个不要求下标连续、能随意增删、查找还快的超级数组。这个类比不是为了讲概念而是为了建立直觉。暴力算法慢往往慢在“查找”这一步线性扫描、循环里再嵌套一层循环去找某个值。而哈希表把查找从 O(n) 打到了平均 O(1)代价是额外的一块内存。所以哈希法在算法题里最常见的形态不是“哈希算法”本身而是“用哈希表优化查找”。三道题的核心其实都是这个动作。1.2 三道题覆盖了哈希的三种常见用法第一道两数之和是哈希的“地基”边遍历边查补数教你的是怎么用哈希表查一个目标值。第二道字母异位词分组开始进阶重点不在查而在“键”怎么设计如何把一类对象映射到同一个 key 上。第三道和为 K 的子数组是哈希和前缀和的结合这时哈希表存放的是“某个值出现了多少次”用到的是计数器思维。如果把哈希表的用法做个归类绝大多数题都逃不出这三种用值做 key 查对象、把对象归并到同一个 key 下、用 key 统计频率。刷完这三道你再看其他 Hash 题会发现套路都很接近只不过包装了一层新的业务描述。1.3 这篇笔记适合谁、怎么读说句实在话LeetCode 刷题最怕的不是不会做而是背了一堆题解之后换一道变形题还是懵。这篇笔记写给三类读者刚开始刷题、不知道 Hash 题从哪下手的人刷过几道但每次都要现想思路的人面试前想快速过一遍哈希经典题型的人。建议的阅读方式不是从头到尾看完代码就行了而是先看思路部分合上屏幕自己敲一遍再回来看细节。算法能力是“手上功夫”眼熟没用。哪怕你现在只能写出暴力版本只要理解了哈希为什么能把复杂度降下来后面的部分消化起来会快很多。2. 第一道题两数之和——最基础的“补数”模型2.1 先把暴力解摆出来看清它慢在哪题目描述很简单给定一个整数数组 nums 和一个目标值 target找出数组中和为目标值的两个数返回它们的下标。暴力做法就是两层循环外层定住一个数内层在它后面找有没有能凑成 target 的另一个数。复杂度是 O(n^2)这个复杂度在 n 到 10^5 的时候基本就要跑几十秒LeetCode 上直接超时。最重要的不是背答案而是想清楚暴力解法重复做了什么每遍历到一个元素都在剩下的数组里线性查找它的“补数”。查找是重复发生的又恰恰是最耗时的。如果能让这一步查找变成 O(1)整个算法就从 O(n^2) 变成 O(n)。哈希表就是用来干这件事的。2.2 核心思路边遍历边找补数对当前元素 nums[i] 来说它要找的那个数不是别的就是 target - nums[i]我习惯把这个值叫“补数”。例如 target9当前数是 2那它要找的就是 7。问题就变成了在已经扫描过的元素里有没有出现过这个补数如果有直接返回。这里有个容易写错的念头先把整个数组一次性塞进哈希表再遍历一遍查询。这样做在数组里有重复元素时会有问题。比如 nums[3,3], target6一次性塞进去之后key3 对应的 value 会被后面的下标覆盖成 1等遍历到第二个 3 时返回 [1,1]两个下标是同一个位置明显错了。更安全的写法是“边遍历边放入”每走到一个新元素先查历史查完再把当前元素写进哈希表。这样天然规避了前后覆盖和“自己配自己”的问题。2.3 关键细节为什么必须先查后放这个顺序问题值得单独拿出来说。假设数组是 [3,3]target6。第一次循环发现哈希表里没有 3把 3 放进去value 是 0。第二次循环查哈希表发现已经有 3取出下标 0返回 [0,1]正确。如果反着来先放再查第二次循环时先把当前下标 1 覆盖进去哈希表里的 3 指向的 value 就变成了 1再查补数 3返回 [1,1]自己配自己错了。所以你去看几乎所有题解都会强调“先查后放”。这不是代码风格问题是逻辑正确性问题。还有一个很容易忽略的点为什么用“值”做 key用“下标”做 value因为查询条件是“值是否出现过”返回结果是“下标”。哈希表的设计应该让查询条件落在 key 上让需要的结果落在 value 上。这个习惯在之后很多哈希题里都会用到。2.4 代码与复杂度public int[] twoSum(int[] nums, int target) { // key: 元素值, value: 元素下标 MapInteger, Integer map new HashMap(); for (int i 0; i nums.length; i) { int need target - nums[i]; // 先查历史中是否存在补数 if (map.containsKey(need)) { return new int[]{map.get(need), i}; } // 查不到再放入当前元素 map.put(nums[i], i); } return new int[0]; }时间复杂度 O(n)空间复杂度 O(n)。每一步操作都是常数级别遍历一次数组就得到答案。空间上多用一个哈希表这就是典型的“空间换时间”。在 LeetCode 的环境下O(n^2) 和 O(n) 的差距就是超时和秒出的差距。2.5 从一个变体说起排序数组的双指针解法两数之和还有一个变体如果数组事先排好序并且不需要返回下标只问是否存在这样两个数那双指针会更好。左指针指向最小值右指针指向最大值根据和的大小移动指针复杂度 O(n)空间 O(1)。但原题要求返回下标而排序会打乱下标信息所以哈希解法更直接。这也引出一个经验题目是否允许排序、是否要求下标、是否要求去重都会影响方案选型。哈希不是唯一的答案但它是适用范围最广的答案。3. 第二道题字母异位词分组——哈希键的设计思维3.1 异位词的判断标准是什么题目给一组字符串要求把“字母异位词”分到同一组。所谓异位词就是字母组成和数量完全相同只是排列顺序不同。比如 eat、tea、ate 是一组而 tan 和 nat 是另一组。暴力做法是两两比较字符串判断字符组成是否相同复杂度 O(n^2 * k)n 是字符串数量k 是平均长度基本不可行。我们需要一个统一的标识同一组异位词应该算出同一个 key不同组的 key 必须不同。这个想通了题目就变成了“设计一个 key 的计算方法”再用 HashMap 聚合。3.2 方案一排序后的字符串作键最经典的做法把每个字符串的字符排序。eat 排序后是 aettea 排序后也是 aettan 排序后是 antnat 排序后也是 ant。于是异位词被映射到了同一个排序结果上用这个排序结果做 keyvalue 是这一组字符串的列表。public ListListString groupAnagrams(String[] strs) { MapString, ListString map new HashMap(); for (String s : strs) { char[] chars s.toCharArray(); Arrays.sort(chars); String key new String(chars); // 如果 key 不存在创建一个新列表再添加 map.computeIfAbsent(key, k - new ArrayList()).add(s); } return new ArrayList(map.values()); }代码里有两个值得学习的点。一是 computeIfAbsent 的用法当 key 不存在时先执行后面的 lambda 创建一个 ArrayList存在就直接返回已有列表。新手很容易写成“先判断有没有 key有就 get 再 add没有就 new 一个”代码会拖沓不少。二是在 Map 中 value 是集合时注意最后返回前要 new ArrayList(map.values())因为 values() 返回的是视图直接返回在某些场景下不够安全。3.3 方案二字符计数作键排序不是唯一的键构造方式。既然题目限制了小写字母那字符集就固定 26 个完全可以用每个字母的出现次数来编码。统计完一个字符串的 26 个字母频次后把频次数组序列化成字符串比如 eat - “1#0#0#...#1#...”a 出现 1 次e 出现 1 次t 出现 1 次其他都是 0。tea 会得到同样的序列。为什么用分隔符 #这是容易忽略的细节。假设把频次数组直接拼成 “123”就无法区分“1、2、3 三个数字”和“12、3 两个数字”这类情况。加上分隔符后每个频次的位置是固定的就不会歧义。我在第一次写这类代码时偷懒没加分隔符结果字符串一长数字跨位拼接分组全乱了。实现代码如下public ListListString groupAnagrams(String[] strs) { MapString, ListString map new HashMap(); for (String s : strs) { int[] count new int[26]; for (char c : s.toCharArray()) { count[c - a]; } 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(s); } return new ArrayList(map.values()); }这个方案的时间复杂度是 O(nk)比排序方案 O(nk*log k) 更快因为不需要排序。代价是代码量变多而且只能在字符集固定时使用。如果字符串里包含大写字母、数字字符集就要扩大计数数组也要对应调整相比之下排序方案天然支持任意字符所以更通用。3.4 一个有意思的脑洞质数乘积键python 圈子里有人提过一个很巧的方案给 26 个字母分别分配一个质数把字符串中每个字母对应的质数乘起来乘积作为 key。因为质因数分解唯一所以乘积相同当且仅当字母组成相同。理论上非常优雅但工程上不实用字符串稍微长一点乘积就会溢出long 也扛不住。你可以拿它来感受一下构造哈希键的灵活性但面试和实际项目中别用这种方案老老实实排序或计数就好。3.5 键的设计三原则做完了这题我总结出的哈希键设计原则有三个唯一性、确定性、不可变性。唯一性是指不同分组不能算出同一个 key确定性是指同一分组必须稳定算出同一个 key不可变性是指 key 放到哈希表里之后不能被修改。第三点尤其要小心。Java 里如果用可变对象当 key比如 ArrayList、StringBuilder放进去之后一旦内容改变它的 hashCode 就会变再 get 的时候哈希表已经找不到原来的位置了。这也是我推荐用排序字符串和计数序列化字符串做 key 的原因String 天然不可变不会踩这个坑。以后你用自定义对象当 key 时一定要重写 hashCode 和 equals并且保证对象内容不变。4. 第三道题和为 K 的子数组——前缀和与哈希的结合4.1 为什么枚举所有子数组不可行题目要求统计数组中和为 k 的连续子数组个数。最朴素的做法是枚举所有起点和终点计算区间和复杂度 O(n^2)。当 n 到了 2*10^4 的量级就是大约 2 亿次运算在 LeetCode 上已经处于超时边缘。这道题的价值在于它看起来是“区间求和”问题但通过一个数学变换可以变成“哈希查找”问题。4.2 前缀和把区间和变成两个前缀和的差定义 prefix[i] 为数组前 i 个元素的和。那么区间 [j, i) 的和可以表示为 prefix[i] - prefix[j]。要求这个区间和等于 k等式就变成prefix[i] - prefix[j] k移项之后prefix[j] prefix[i] - k这个式子很关键。它告诉我们当遍历到某个位置 i 时我们不需要再去枚举起点 j只需要知道历史上有多少个 j 满足 prefix[j] 等于 “当前前缀和 - k”。换句话说区间计数问题被转换成了“历史值出现次数”的问题。这正是哈希表能高效解决的事情。4.3 哈希表在本题中的作用历史前缀和的计数器本题的哈希表 key 存的是前缀和的值value 存的是这个前缀和出现的次数。为什么用“次数”而不是“下标”因为同一个前缀和在数组里可能出现在多个位置题目只要求统计个数不需要知道具体是哪些位置所以计数就够了。每次循环要做两件事。第一件把当前前缀和 cur 更新为 cur num第二件查一下历史里出现过多少个 cur - k累加到答案然后把当前 cur 的计数加一。核心代码如下public int subarraySum(int[] nums, int k) { // key: 前缀和的值, value: 出现次数 MapInteger, Integer prefixCount new HashMap(); // 重要前缀和为 0 的情况一开始就出现一次 prefixCount.put(0, 1); int cur 0; int ans 0; for (int num : nums) { cur num; // 查历史有多少个前缀和等于 cur - k ans prefixCount.getOrDefault(cur - k, 0); // 再更新当前前缀和的计数 prefixCount.put(cur, prefixCount.getOrDefault(cur, 0) 1); } return ans; }这两句的顺序不能反。如果有人把更新写在查询之前在 k0 时就会出问题。比如 nums[1,-1], k0遍历完第一个元素后 cur1第二个元素时 cur0如果先更新 map把 0 的计数加一再查询 cur-k0 就会把刚放进去的“当前前缀和”也算进去多算了一个不存在的子数组。正确的逻辑是子数组需要由“历史前缀和”和“当前前缀和”构成当前这轮的前缀和不应该被当成历史。所以必须先查后更新。4.4 为什么初始要放一个 prefix(0)1这个细节我第一次做的时候漏了导致边界用例一直错。前缀和序列其实包含一个隐含的初始值什么元素都不取时前缀和是 0。这个值必须提前放进哈希表计数为 1。举例nums[1], k1。遍历到第一个元素时 cur1查询 cur-k0。如果 map 里没有 0答案就是 0但正确答案是 1因为子数组 [1] 本身就满足条件。有了 prefix(0)1查询才能命中。所以凡是用前缀和计数的题目第一步永远是把 0 放进哈希表代表“从数组开头到当前位置的这段区间”这个可能。还有一点比“先查后更新”更隐蔽为什么不能先把整个数组的前缀和都算出来、统计好次数再遍历查询因为这样会破坏顺序约束。子数组要求终点在起点之后也就是 j 必须小于 i。一次性统计会把未来位置的前缀和也当成历史来用导致多算。举个简单例子nums[1,-1], k0前缀和序列是 0,1,0如果先统计0 出现 2 次1 出现 1 次再遍历到第一个前缀和 0 时查询 0会把后面那个 0 也算进答案而它其实来自终点之后。所以这道题必须边遍历边更新顺序和动态性都是正确性的一部分。4.5 复杂度与适用场景时间复杂度 O(n)每个元素只处理一次。空间复杂度 O(n)哈希表最多存 n 个不同的前缀和。这个解法的最大优点是它对负数一无所知不管数组里有没有负数逻辑都成立。说到负数很多人会条件反射地想到滑动窗口但要记住滑动窗口依靠窗口内和的单调性来移动指针一旦数组含有负数和就不再单调滑动窗口就失效了。所以遇到“连续子数组和”类的题目我的习惯是先想前缀和只有明确数组全为正数时才会考虑双指针或滑动窗口。前缀和加哈希是一个通用性强得多的组合可以延伸到很多问题比如“和可被 K 整除的子数组”“二维矩阵的子矩阵和”等本质都是把区间信息转换成前缀差再用哈希加速查询。5. 做完三道题后我想叮嘱你的几件事5.1 哈希表操作细节速查刷这三道题的过程中我发现很多问题不是思路没想到而是对哈希表的“操作细节”不够敏感。整理了一张自己常用的检查清单场景常见误区正确做法判断 key 是否存在map.get(key) null用 containsKey除非你能保证 value 不会为 null计数时更新分两次 get 和 put用 getOrDefault 一次性处理以值为 key 存下标重复值会互相覆盖想清楚覆盖会不会影响答案两数之和要用边遍历边放遍历时修改容器在 for 循环里对 map 做增删需要时先记录循环外处理自定义对象做 key只有 equals 没有 hashCode两者必须同时重写初始化容量直接 new HashMap()数据量大时预估容量减少扩容开销第六点在刷题时影响不大但在工程里很值得重视。HashMap 默认容量是 16负载因子 0.75也就是到 12 个元素就会扩容。如果数据量大且能预估规模构造时就指定初始容量能省掉不少扩容操作的耗时。5.2 我实际踩过的三个坑第一个坑在两数之和。我第一次提交时把 map.put 写在了 containsKey 判断前面结果遇到 [3,3] 和 target6 直接返回了 [1,1]调试了半天才发现是“先放后查”导致的自我配对。从那以后凡是遍历一遍数组需要配对查找的题我都会默认用“先查后放”的顺序。第二个坑在字母异位词分组。我用计数法构造 key 时偷懒把频次数字直接拼起来没有分隔符结果两组不同的频次在拼接后出现了相同的字符串导致分类错乱。加上分隔符之后问题才消失。这个教训是凡是把数组序列化成字符串做 key一定要保证序列化是可逆且无歧义的分隔符、固定长度都是为此服务的。第三个坑在“和为 K 的子数组”。忘了把前缀和 0 初始化进哈希表连续几个测试用例都少算答案。后来我总结出一个口诀凡是前缀和计数类题目第一行必然是 map.put(0, 1)。这不算死记硬背它对应的语义是“从头开始的区间也是合法区间”。5.3 什么时候别急着用哈希聊了这么多哈希最后还是想说一句不是所有题都适合哈希。比如说三数之和、四数之和这类需要输出所有不重复组合的题目哈希反而会因为去重逻辑变得很繁琐排序加双指针才是正解。再比如内存敏感的场景用哈希表额外占用 O(n) 空间如果题目对空间有强约束就得考虑其他方案。我的做题流程一般是这样先写暴力想明白慢在哪一步然后问自己“这一步是不是在反复查找某个值”。如果是就看看能不能用哈希表把查找变成 O(1)如果键不好设计、空间不允许、或者还要额外维护顺序再考虑排序、双指针、甚至二分。这三道题做完我对“什么时候用哈希”有了比较明确的直觉当问题里出现“找某个数”“统计某个值出现的次数”“按某个特征分组”三类动作时哈希大概率是值得优先尝试的方案。把这三道题的思考过程内化掉后续遇到大量 Hash 相关的题你会发现自己变快了不少因为核心套路其实就是今天说的这些。