说实话我第一次照着《代码随想录》刷到 Day10 这三道题的时候心里是有点不服气的。202 快乐数、1 两数之和、454 四数相加Ⅱ名字一个比一个基础看起来像是哈希表专题里最轻松的一天。结果真上手才发现快乐数卡了我二十分钟两数之和在先查还是先存上翻了车四数相加Ⅱ又差点被暴力思路带偏。现在再回头看这三道题根本不是三道互不相干的小题它们刚好把哈希表的三种典型用法一次性交给了我判重、记下标、数次数。如果你也是第一次进入哈希表这章或者刷完题但总觉得理解得不够透这篇文章就是为你写的。我会把自己当初踩过的坑、最后怎么把思路理顺的过程连同完整代码和复杂度分析一起放出来。读完你不仅可以独立写对这三道题还可以顺手把什么时候该用哈希、用哪一种哈希这套判断方式带走。1. 把快乐数读成链表题一次看穿 202 的本质1.1 本质不是算平方和而是检测循环先说题目对于一个正整数每一次把它替换成它每个位置上的数字的平方和如果最终能得到 1就认为它是快乐数如果陷入了一个不包括 1 的无限循环就认为不是快乐数。绝大多数人第一次读到这句话注意力都会放在怎么求各位数字的平方和上于是开始反复试算。我自己就是这样按照题意把 19 算到 1把 2 一直算下去发现 2 永远到不了 1却说不清它到底什么时候该停。其实这道题真正考察的地方不是数学而是状态检测从 n 出发我们会得到一个序列n - f(n) - f(f(n)) - ...。如果序列中出现某一个已经出现过的数那么后面的结果一定会完全重复因为每次计算规则完全相同。这跟链表里检测有没有环是同一个模型每一个数相当于链表节点计算平方和的函数相当于 next 指针。序列要么进入值为 1 的节点后结束要么在一个环里反复打转。所以判断快乐数的关键就是判断这个数字链表有没有环。我后来还给这个直觉补了一个简单的数学支撑。对任意一位数字 dd² ≤ 81一个 k 位数 n它各个数位平方和最大也就是 81k。当 n 足够大时81k 会显著小于 n 本身所以经过一轮转换数字会快速缩小并落到一个有限范围内例如三位数换算后最大 243。范围有限而变换是确定性的那么迟早会出现重复。这解释了为什么不是快乐数的数字一定会循环而不是无限发散。1.2 最直接的写法哈希集合记录出现过的数字想清楚检测循环之后代码其实很简单。用一个集合记录所有已经出现过的数位平方和结果每次计算出来先检查它是不是已经在集合里如果已经是 1直接返回 true如果这个结果已经在集合里说明进入循环返回 false否则把结果加入集合继续下一次计算。C 版本可以这样写class Solution { public: int bitSquareSum(int n) { int sum 0; while (n) { sum (n % 10) * (n % 10); n / 10; } return sum; } bool isHappy(int n) { unordered_setint seen; while (n ! 1) { if (seen.count(n)) return false; seen.insert(n); n bitSquareSum(n); } return true; } };Python 版本同样直接class Solution: def isHappy(self, n: int) - bool: def get_next(x: int) - int: total 0 while x: x, digit divmod(x, 10) total digit * digit return total seen set() while n ! 1: if n in seen: return False seen.add(n) n get_next(n) return True这里有一个很值得注意的细节往集合里存的是每一轮计算后的数本身而不是某一个中间数字。比如 n 2序列是 2、4、16、37、58、89、145、42、20、4当我们第二次遇到 4 的时候就立刻可以判断回到了循环不用再继续算下去。集合的作用就是提供一个 O(1) 的记忆让我们知道某个数字已经来过。1.3 快慢指针同样能解而且空间更省如果不额外开集合也可以用链表判环里经典的快慢指针。慢指针每次走一步也就是算一次平方和快指针每次走两步也就是连续算两次平方和。如果二者最终相遇说明存在环但此时需要额外判断相遇的点是不是 1如果是 1那它其实是一个快乐的环如果不是才说明不快乐。class Solution: def isHappy(self, n: int) - bool: def get_next(x: int) - int: total 0 while x: x, digit divmod(x, 10) total digit * digit return total slow n fast get_next(n) while fast ! 1 and slow ! fast: slow get_next(slow) fast get_next(get_next(fast)) return fast 1用快慢指针的好处是空间复杂度从 O(k) 降到了 O(1)这里的 k 是循环前那一段链的长度加环长度。实际刷题时用集合版本最容易写对也最容易解释快慢指针版本更符合这题本质是链表环检测的认知也适合拿来应付追问。两种写法我都建议在本地跑一遍尤其是快慢指针的退出条件多写几次才能形成肌肉记忆。我在实测中发现快乐数这道题最容易被不熟悉 divmod 的写法坑到。Python 里先取模再整除、或者直接用一个循环加临时变量本质上都一样但必须注意算出新 n 的时候不能让旧 n 一起被改变。单独写一个 get_next 函数能避免很多啼笑皆非的 bug。2. 两数之和最简单的题最容易在边界上翻车2.1 暴力法不是没用它是高效解法的起点两数之和几乎是所有刷题人的第一道题。题目给一个整数数组和一个目标值 target要求返回两个下标使得这两个数相加等于 target。很多人第一反应就是双层循环把每一对都试一遍for (int i 0; i nums.size(); i) { for (int j i 1; j nums.size(); j) { if (nums[i] nums[j] target) return {i, j}; } }这个写法在数组很小的时候没有任何问题。但它真正告诉你的信息是对于每一个 nums[i]我们不得不在后面的所有元素里线性查找另一个数因此总代价是 O(n²)。如果你能把在后面查找这一步变成 O(1)整体就能变成 O(n)。而能把查找变成 O(1) 的常见容器就是哈希表。我见过不少同学刷过这道题却说不清暴力法为什么慢原因在于他们从没用查找成本的角度分析过代码。每一个内层循环就是一次线性扫描一次扫描 O(n)一共 n 次所以是 O(n²)。理解了成本来源你自然就会想能不能边扫描边把已经见过的元素记录下来这样后续每次查找都直接命中。2.2 哈希表怎么把查找变成 O(1)这里我们使用的不是无序集合而是哈希映射把值作为 key下标作为 value。理由是题目要求返回下标而集合只能告诉我们值是否存在不能告诉我们它在哪里。遍历数组时对当前元素 num我们想找 target - num 是否已经出现在前面。如果已经出现从哈希表里取出它的下标和当前下标一起返回如果没有出现就把当前 num 和它的下标存进哈希表。class Solution: def twoSum(self, nums: List[int], target: int) - List[int]: seen {} for i, num in enumerate(nums): gap target - num if gap in seen: return [seen[gap], i] seen[num] i return []时间复杂度 O(n)空间复杂度 O(n)。这段代码的核心是一句话利用已经遍历过的元素建立字典边遍历边查而不是先建好整个字典再遍历。2.3 先查后存四个字是我翻车最惨的地方两数之和最经典的坑就是遍历当前元素时先把它存进哈希表再去查。我用一个例子说明为什么不行数组 [3, 2, 4]target 是 6。如果先存再查遍历第一个元素 3 时先把 3 存进哈希表然后查 target - 3 3结果发现哈希表里已经有 3于是返回 [0, 0]。但题目要求两个下标必须不同这显然错了。改成先查后存就安全了遍历 3 时查 3 是否存在此刻哈希表为空查不到再把 3 存进去遍历到 2 时查 4 是否存在也查不到存 2遍历到 4 时查 2 是否存在能找到下标 1返回 [1, 2]。整个过程不会出现同一个下标和自己拼成答案的情况。还有一个容易忽略的点数组中可能出现重复元素。比如 nums [3, 3]target 6。答案应该是 [0, 1]。用先查后存的逻辑走到第二个 3 时查 target - 3 3发现前面的 3 已存在返回 [0, 1]这是正确的。如果我们提前把整个数组都存进去就会在遇到第一个 3 时就查到另一个 3结果也可能对但如果是同一个值出现三次以上提前建表容易引起下标覆盖问题。为了逻辑清晰我建议固定使用先查后存的顺序这样任何情况下都不用担心重复值干扰。2.4 这道题的变形值得顺着追问想一遍两数之和几乎不可能是你的最后一题。面试官常在此基础上追加几个问题如果数组是有序的可以排序后双指针从两端向中间移动时间和空间能进一步优化。但注意双指针要求返回的是值还是下标如果返回下标排序后下标会变需要额外记录。如果要求返回所有不重复的组合而不是一组下标就需要对结果去重。一个思路是把哈希表的值从单个下标改成下标列表每次查询后要把所有对应下标都取出来排列另一个更常见的思路是先排序再用双指针。三数之和可以看成固定一个数然后对剩余部分做两数之和。但因为要处理去重直接照搬两数之和的哈希方案会导致下标、去重逻辑都很麻烦所以一般先用排序 双指针。把这些变形想明白两数之和才算真正吃透了。我自己的经验是不要急着把所有变形代码都写完先把为什么需要哈希先查后存这两个点论述清楚变形题只是在它们上面做文章。3. 四数相加Ⅱ四个数组两两分组的盘算3.1 暴力四层循环的问题远比你想的大454 题给四个长度相同的整数数组 nums1、nums2、nums3、nums4要求统计所有满足 nums1[i] nums2[j] nums3[k] nums4[l] 0 的四元组个数。最直观的思路是四层循环i、j、k、l 各扫一遍把所有组合都检查一次。如果每个数组长度为 n组合数就是 n⁴。力扣里 n 最大能给到 200200⁴ 是 16 亿这已经超出了 Java 或 C 单秒能轻松处理的范围Python 下的纯循环更不用想绝对超时。我第一次做这题的时候先想的不是优化而是反正 n 才 200说不定 PyPy 能扛过去结果当然被打脸。与其仰赖硬件不如从数学上把事情变简单四个变量太多能不能减少变量个数3.2 分组抵消把 abcd0 变成 ab -(cd)观察等式abcd0 等价于 ab -(cd)。这意味着我们不需要同时枚举四个数可以把问题拆成两个阶段枚举 nums1 和 nums2 中所有组合算出每个 ab 的和用一个哈希表记录这个和出现了多少次枚举 nums3 和 nums4 中所有组合对每个 cd去哈希表中查询 -(cd) 出现了多少次把所有次数累加起来。这样时间复杂度是 O(n² n²) O(n²)。n200 时实际要处理的组合只有 40000 次比 16 亿小了整整四万倍。这是降维在算法题里最直接的体现把四个变量的等式通过移项变成两个独立问题的匹配。空间复杂度也是 O(n²)因为哈希表最多可能出现 n² 个不同的和。但你不需要同时存四个数组的数据只需要存前两个数组的组合结果。3.3 代码实现与计数累加的细节Python 写起来非常短class Solution: def fourSumCount(self, nums1: List[int], nums2: List[int], nums3: List[int], nums4: List[int]) - int: from collections import defaultdict counter defaultdict(int) for a in nums1: for b in nums2: counter[a b] 1 result 0 for c in nums3: for d in nums4: result counter[-(c d)] return resultC 版本也几乎是同构的class Solution { public: int fourSumCount(vectorint nums1, vectorint nums2, vectorint nums3, vectorint nums4) { unordered_mapint, int counter; for (int a : nums1) for (int b : nums2) counter[a b]; int result 0; for (int c : nums3) for (int d : nums4) result counter[-(c d)]; return result; } };有三处细节值得你注意。第一counter 的 value 是出现次数而不是下标。因为题目统计的是组合数量只要 nums1[i]nums2[j] 等于某个值而 nums3[k]nums4[l] 能跟它抵消那么每一个匹配都构成一个四元组计数。如果 ab 出现了 3 次而 -(cd) 也出现了 2 次这一组 c、d 就能贡献 3 个计数。第二查询不存在时unordered_map 的 operator[] 会默认插入一个值为 0 的键所以 result 加 0 也没有问题。如果怕频繁创建默认键导致哈希表膨胀可以先检查 find 再累加不过对这道题来说差别可以忽略。第三counter 的 key 可以是负数也可以是 0没有任何问题。哈希表对 key 的类型没有非负限制不像用数组下标那样需要做偏移处理。3.4 别被名字骗了它不是四数之和力扣 18 题也有一道题叫四数之和但那是同一个数组里选四个数且要求结果不重复。454 是完全不同的模型四个独立数组只要下标组合满足等式即可不同数组之间不存在互相竞争不需要去掉重复三元组的复杂判断。很多人刷到后面把两道题混淆问为什么 454 不用排序去重其实原因就是我们把 ab 当作一个整体cd 当作另一个整体两边来自不同的数组不存在同一个值在不同位置被反复使用的限制唯一可能的重复来自相同和值的频次而计数器恰好把这种情况数进去了。我第一次做 454 时还想过能不能只用一个哈希表。理论上当然可以比如先遍历 nums1、nums2、nums3把 abc 存进哈希表再遍历 nums4 查 target - d但这会把空间复杂度变成 O(n³)而且三次组合的中间计数也需要特别小心。两两分组之所以标准是因为它同时把时间和空间压到 O(n²)在 n 最大 200 的约束下是最平衡的答案。4. 一连串题做下来哈希表的三个开火信号4.1 判重用 set记录我见过谁快乐数给我们的第一个信号是你是否需要知道某个状态是否出现过。题目没有要求返回次数没有要求保留唯一标识只需要判断过去是否见过。这种场景用一个无序集合即可。凡是链式状态转移、递归展开、DFS 剪枝去重等场景都可以套用同一逻辑把状态压进集合一旦再次出现就说明已经处理过。4.2 记下标用 map记录值在哪里两数之和需要的是位置信息光用集合不行。什么时候值 - 下标这种映射会成为刚需凡是要求返回下标、要求定位元素的题目基本都需要 map。比如两数之和的变体、字符出现位置的统计、LRU 缓存里的快速查找都会用到这种结构。4.3 数次数用 map记录它出现过几次四数相加Ⅱ需要的既不是判重也不是下标而是频次。它要统计的是匹配种数所以哈希表的 value 要承担计数功能。这类问题的经典标志是题目要求多少种组合多少种方案能不能凑出目标值并且每个数字只能用一次一旦出现计数需求把 value 设为频次几乎是必然选择。题目我们想记住什么适合的容器value 含义202 快乐数历史状态set无1 两数之和值的下标map下标454 四数相加Ⅱ和值出现次数map频次4.4 哈希表不是万能钥匙别养成路径依赖看到查找就上哈希表是新手容易形成的习惯。哈希表虽然查找平均 O(1)但常数比数组大空间也高。如果数据范围是已知且有限的比如小写字母、0-26、ASCII 字符用数组当哈希表更轻更快如果数组已经有序二分查找或双指针可能不需要额外空间。选择容器前应该先问几个问题我需要判断存在还是返回下标值域是否有限是否需要保持顺序哈希表只是其中一个正确答案不是唯一答案。我自己的判断顺序很简单先想如果我只有 O(n) 时间需要额外记什么再去挑容器。快乐数要记历史状态就用 set两数之和要记值下标就用 map四数相加要记和次数就用 map。容器只是把意图落到代码里的工具。5. 我的 Day10 刷题复盘这三题该怎么安排节奏5.1 建议的做题顺序与时间分配如果你今天刚准备开启哈希表专题我的建议顺序是两数之和、快乐数、四数相加Ⅱ。理由也很实际两数之和的值-下标最直观能快速建立哈希是空间换时间的直觉快乐数把哈希从找另一半切换到记录历史完成对 set 用法的补充四数相加Ⅱ再上一个台阶需要你主动设计分组策略而不是照搬前面的代码。时间上第一次做的话每道题留 25 到 40 分钟都正常。如果卡住超过 20 分钟不要硬扛看一眼题解思路再自己重写代码。刷题的节奏不是比谁先写完而是比谁能在大后天还能凭自己的话把思路解释清楚。5.2 一个能防止你掉进背代码陷阱的复盘清单刷完这三道题后我建议你关掉题解回答下面几个问题快乐数里集合记录的是什么为什么记录它就能判断循环两数之和为什么必须先查后存把自己的解法改成先存后查能不能用一个测试用例证明它会错454 题的时间复杂度为什么是 O(n²)如果不做两两分组暴力四层是多少454 题的哈希表 value 为什么是次数而不是下标或布尔值能不能把快乐数改成快慢指针版本并解释空间从 O(k) 变成 O(1)?这几个问题能答上Day10 的核心就不会只是今天刷了三道题而是一整套可复用的哈希用法。5.3 后续可以把这套打法用到哪里去快乐数的环形检测思路会在环形链表、寻找重复数、判断循环小数等题目里再次出现两数之和的先查后存模板可以顺延到两数之和-数据结构设计、和为 K 的子数组、三数之和的思路推导里四数相加Ⅱ的两两分组思想则会在很多多个集合凑目标值的题里反复出现比如把四元组拆成两组独立哈希本质上都是 454 这题的变形。从 Day10 往后你会发现哈希表几乎是无处不在的。它本身不藏很高深的算法却处处考验你能不能判断一个信息该不该被额外记住、用什么样的结构去记。只要把这三道题背后的用途梳理清楚后面的哈希题再变化你也只是在这三个信号之间做组合。我在实际操作中还有一个体会这三道题做完最好把它们放进同一个笔记页写上一行哈希三用途set 判重、map 存下标、map 数次数。以后每次刷到哈希题先对号入座再动手写代码思路会清爽很多。真心建议你把这三题当作哈希表的基石题而不是单纯的打卡题因为后面的路还长但基础就这么几块。
