刷 LeetCode 的人应该都见过 202 这道题——快乐数。第一次看到题目描述的时候我的第一反应是这有什么难的把每一位拆出来平方累加最后等于 1 就返回 true 呗。可等我真正动手写代码才发现自己还是天真了——如果这个数不是快乐数它会无限循环下去你怎么知道该什么时候停下来这题的真正考点根本不是如何计算平方和而是如何用一个可证明的终止条件来结束迭代。这篇文章我用 C 语言把三种主流解法都实现了一遍哈希表记录法、快慢指针法、数学规律法。三种解法的思路完全不同但都能在有限步内给出确定答案。无论你是刚开始刷题的初学者还是准备面试想系统性过一遍哈希和链表专题的开发者把这一题吃透都不亏。代码可以直接抄但背后的循环检测思想才是这题真正值钱的地方。1. 题目拆解快乐数到底在考什么1.1 从题目描述到核心考点先过一遍题目定义对于一个正整数每一次将该数替换为它每个位置上的数字的平方和然后重复这个过程直到这个数变为 1也可能无限循环但始终变不到 1。如果能变为 1那么这个数就是快乐数。举两个例子感受一下差异。19 是快乐数1² 9² 828² 2² 686² 8² 1001² 0² 0² 1到 1 了结束返回 true。2 不是快乐数2² 44² 161² 6² 373² 7² 585² 8² 898² 9² 1451² 4² 5² 424² 2² 202² 4注意看从 4 开始转了一圈又回到 4形成闭环。之后无论怎么迭代都只会在 4、16、37、58、89、145、42、20 这几个数之间打转永远到不了 1。所以这个题的核心考点就三个第一你能不能在第一次接触时意识到这里有循环。很多人上来就写while(n ! 1) n getNext(n)对快乐数没问题但遇到 2 这种数就直接死循环。严格说实现层面少了终止条件逻辑层面少了“循环检测”这个意识。第二你会不会选择合适的数据结构来检测循环。最自然的是哈希表把见到的数字存起来重复即循环。C 语言没有内置 HashSet怎么用数组模拟怎么分析数据范围这就是基本功。第三你懂不懂 Floyd 判圈算法。把数字变换抽象成链表快乐数问题就变成了链表判环问题。这是面试官非常喜欢的“场景转换”能力。1.2 为什么 C 语言解这题有特殊性网上很多题解用 Python 或 Java自带 Set 接口直接往集合里丢数就行几行代码搞定。但 C 语言不一样没有现成的哈希表你必须自己决定用什么结构。这个决定本身就在考察你对问题规模的理解。这里有一个非常关键的性质对于 32 位 int 范围内的数最多只有 10 位数字每一位最大是 9所以任意一个数的各位平方和最大不会超过 9² × 10 810。也就是说不管初始值多大只要执行一次 getNext 操作得到的中间结果一定落在 0 到 810 之间。这个性质直接简化了两个问题用数组模拟哈希表时数组只需要开 1000 左右不需要真正的哈希函数和冲突处理。因为中间结果被限制在这么小的范围里整个迭代序列必然快速进入两种状态之一要么到 1要么进入 4 那个循环。这也从侧面说明了为什么哈希表和快慢指针都能在有限步内结束。很多 C 语言的题解喜欢开一个很大的数组比如 10001其实没必要分析清楚数据范围能省不少内存也更体现水平。2. 解法一哈希表记录法2.1 思路与哈希表选型思路很直接把每次计算得到的中间值记下来如果发现某个值已经出现过说明序列进入了循环。因为数字变换的下一个值是唯一确定的一旦出现重复后面就会无限重复同一段序列。如果这个重复发生之前还没到 1那这个数就永远不可能变成 1。这个逻辑相当于在一条“状态链”上找重复节点。关键问题是用什么结构记录已经出现过的数字在 C 语言里最简单高效的方案是用布尔数组模拟哈希表bool seen[1000] { false };为什么数组大小为 1000 就够前面算过int 范围内任何数经过一次变换后结果最大不超过 810。因此每次迭代产生的 n 都是一个小于 1000 的数直接用 n 作为数组下标就能完成“查询是否见过”和“标记已见”两个操作。这种方式其实是“直接寻址哈希”因为关键字范围小且确定不需要设计哈希函数。这也是哈希表的一种特例面试时如果被问到可以大方地说出来比笼统地说一句“用哈希表”得分高。另一个小细节数组哈希表里的每一个位置只有两种状态见过或没见过所以用bool数组就够了不需要计数。如果误用了int数组也是可以的但没必要多占内存。这也是 C 语言里值得注意的思维习惯。2.2 C 语言实现与边界处理完整代码如下#include stdio.h #include stdbool.h int getNext(int n) { int sum 0; while (n 0) { int d n % 10; sum d * d; n / 10; } return sum; } bool isHappy_hash(int n) { bool seen[1000] { false }; while (1) { n getNext(n); if (n 1) { return true; } if (seen[n]) { return false; } seen[n] true; } }这里有一个非常容易踩的坑必须先执行n getNext(n)再去访问seen[n]。如果你直接写成if (seen[n])而初始 n 是一个很大的数比如 2147483647那数组就越界了程序行为未定义。这在 LeetCode 上可能表现为随机报错或答案错误在本地可能表现为段错误。说说这段代码的执行流程。进入循环后先把当前数变换到下一状态。如果下一状态是 1直接返回 true。如果已经见过这个状态说明前面走过这条路形成了环返回 false。否则把这个状态标记为已见继续循环。为什么这个循环一定会终止因为每次迭代后 n 都落在 0 到 810 之间而布尔数组大小是 1000最多只能标记 1000 个不重复的状态。抛开到 1 的情况如果一直重复不了那最多 1000 次迭代后必然出现重复状态。所以时间复杂度上界是有保证的。实测下来这个解法的时间表现非常稳定。因为实际迭代次数远小于 1000大多数数字在几十步内就出结果了。空间上固定大小数组可以认为是 O(1)。3. 解法二快慢指针Floyd 判圈3.1 把数字变换看成链表如果你刷过链表判环的题目看到快乐数会觉得特别眼熟。我们可以把每一次数字变换看成链表上的next指针跳转n的下一个节点就是getNext(n)。举个例子对于 2状态链是2 → 4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4 → 16 → ...这个序列进入了一个环等价于链表有环。对于 19状态链是19 → 82 → 68 → 100 → 1 → 1 → 1 → ...进入了一个自循环的“1”节点等价于链表遇到了一个特殊节点。所以判断一个数是不是快乐数就变成了判断这条“虚拟链表”是否有环以及环中是否有 1。Floyd 判圈算法正好解决这个问题。Floyd 判圈的核心思想是用两个指针慢指针每次走一步快指针每次走两步。如果有环快指针最终会追上慢指针两者相等如果无环快指针会先到达终点。对应到快乐数里终点就是 1。因为getNext(1) 1所以快指针会在 1 的位置上原地打转。只要快指针变成 1就可以直接判定是快乐数。为什么快慢指针一定会相遇可以这样理解当慢指针进入环之后快指针一定已经在环里了。此时快指针相对慢指针每次移动一步相当于在环形跑道上每轮追逐缩小一步距离。环的长度有限所以迟早会追上。3.2 完整实现与充分性分析C 语言代码如下bool isHappy_floyd(int n) { int slow n; int fast getNext(n); while (fast ! 1 slow ! fast) { slow getNext(slow); fast getNext(getNext(fast)); } return fast 1; }这里的初始化有个小讲究slow从 n 出发fast先走一步从getNext(n)出发。这样做的原因是如果不让快指针先走一步那么循环条件slow ! fast在第一次判断时就不成立循环直接退出程序会错误地把所有数都判为快乐数。这是初学 Floyd 判圈最容易犯的错。循环体内慢指针走一步快指针走两步。我用了嵌套的getNext也就是fast连续变换两次。可能有人会担心如果fast已经变成 1 了再调用getNext会不会出现问题不会因为getNext(1) 1它会一直停在 1不会越界也不会变成负数。循环退出的条件有两个要么快指针碰到 1说明是快乐数要么快慢指针相等说明检测到环不是快乐数。这里还有一种情况慢指针先到 1快指针还没到 1。慢指针到 1 后也会原地打转等快指针追上它此时slow fast但两者的值都是 1所以fast 1为 true返回结果依然正确。因此不需要单独判断 slow 是否为 1。时间复杂度上每次迭代仍然是执行若干次getNext每个节点的计算成本是 O(log n)迭代次数有限总体很快。空间上只用了两个整数变量是严格的 O(1)比哈希表解法更省内存。4. 解法三数学规律法4.1 唯一循环的发现与证明思路这个解法知道的人不多但一旦知道就会觉得这题原来可以这么简单。数学上已经证明在快乐数的迭代过程中除了 1 之外有且只有一个非 1 的循环4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4所有不是快乐数的数迭代若干次后一定会进入这个循环没有别的可能性。这个结论是怎么来的思路大致是因为任意数经过一次变换后都落到 0 到 810 之间所以整个状态空间有限。在这个有限集合上可以用穷举或反证的方式证明最终只会收敛到 1或者进入上面那一个环。面试时你不一定需要严格证明但最好能口头解释清楚“为什么可以这样判断”而不是直接背结论。一旦接受了这个结论代码就可以写得非常短只需要不断迭代如果中途变成 1返回 true如果中途变成 4返回 false。因为 4 是唯一循环的入口之一一旦落到 4后面必然在循环里打转永远到不了 1。为什么判断 4 就够了而不是把 16、37 这些数都列出来因为 16 继续算会变成 3737 会变成 58最后都会回到 4。所以哪怕当前值是循环里的其他数继续迭代下去也总会遇到 4。用一个等价的判断就可以覆盖整个循环。4.2 最短实现代码bool isHappy_math(int n) { while (n ! 1 n ! 4) { n getNext(n); } return n 1; }看到这段代码很多人会愣一下因为实在是太短了。循环条件写成n ! 1 n ! 4意思是只要没到 1 也没到 4就一直算下去。退出循环后如果 n 是 1说明是快乐数如果 n 是 4说明进入了坏循环。这里有一个边界情况要提醒如果入参是 0这段代码会陷入死循环因为getNext(0) 0而 0 既不等于 1 也不等于 4会一直在循环里出不来。不过题目明确说了输入是正整数所以 0 不在考虑范围内。如果想让代码更健壮可以加一个if (n 0) return false;的判断。从工程角度说这个解法的时间复杂度也是 O(log n) 级别的迭代次数空间 O(1)。代码量最小运行速度最快。但它依赖数学结论面试时如果只写这一版建议把前面两种解法的思路也准备好避免被追问时答不上来。5. 三种解法对比与面试推进策略5.1 复杂度与适用场景对照三种解法放在一起对比差异很清晰解法时间复杂度空间复杂度代码量直观程度适用场景哈希表记录法有限迭代约几十次O(1)固定数组中高教学首选最容易讲清楚快慢指针法有限迭代约几十次O(1)中中面试重点空间最优数学规律法有限迭代约几十次O(1)短低竞赛技巧加分项时间复杂度和迭代次数可以进一步解释。由于中间结果被限制在 0 到 810 之间哈希表法最多迭代 1000 多次就一定会有重复快慢指针法也必然在有限步内相遇或碰到 1。实际跑起来绝大多数数字在 20 步以内就出结果了。有人会提到 O(log n)严格来说这里的 n 是输入数字每一位的平方和计算需要 O(log n) 时间但迭代次数本身与 n 的关系不大分析复杂度时不要混淆。空间复杂度这块哈希表法如果用布尔数组是固定大小严格说 O(1)如果从抽象的“集合”角度看集合中最多存储所有中间状态数量有上界也是常数。快慢指针和数学法都是 O(1)。实际项目里遇到类似的状态循环检测问题比如配置文件的循环引用、协议解析中的状态机回环快慢指针这套思路都能直接迁移。我见过有人在数据流处理中用类似思路检测重复模式比维护一张大哈希表省很多内存。5.2 面试时怎么循序渐进地讲如果是在面试场景里我的建议是分三层递进。第一层先讲哈希表记录法。这是最自然的思路把见过的状态存下来出现重复就停止。面试官最想看到的是你能分析出中间结果的范围并且能具体到“数组开多大”这个细节这比空泛地说“用 unordered_set”要有力得多。第二层面试官大概率会问“能不能优化空间”。这时候引出快慢指针把数字变换类比成链表说明你懂 Floyd 判圈。这里要主动讲清楚为什么快慢指针一定会相遇以及初始值为什么要让 fast 先走一步。第三层作为加分项可以提数学规律法。先写出唯一的循环再给一个两行代码的解法。面试官一般会眼前一亮因为这展示了你对题目更深层的理解。但要注意数学法最好放在最后讲并且把前两种思路讲透否则容易显得像背题。如果面试官继续追问数学法的正确性可以这样回答任意数变换一次后都会落到 810 以内这个有限状态空间里只有 1 和那个已知循环两个吸引子这是可以穷举验证的结论。不需要把完整证明背出来但要表现出你理解这个结论的来源而不是死记硬背。6. 常见问题与避坑实录6.1 高频报错与逻辑问题这个题代码看起来短实际写起来容易出问题的地方不少我整理了一下。第一个经典错误是死循环。很多新手直接写while (n ! 1) { n getNext(n); }输入 2 就直接卡死。原因就是没有处理非快乐数的循环情况。这个错误几乎每个人都犯过我自己第一次写也栽在这里醒来之后才意识到这不是计算问题而是缺少终止条件。第二个经典错误是数组越界。哈希表法里如果写成seen[n] true; n getNext(n);顺序反了而且 n 初始是一个很大的数直接访问seen[2147483647]越界。第三个问题是 getNext 函数本身写错。常见的错误是把取余和除法顺序搞反。正确的写法是先d n % 10计算平方再n / 10。如果你先除再取余会漏掉或者重复处理某一位。另外注意sum d * d这里不要写成sum d * 2这种笔误很隐蔽输出结果会莫名奇妙的。第四个问题是快慢指针初始值。如果写成int slow n; int fast n; while (slow ! fast) { ... }循环一次都不会进去直接返回 true错得离谱。记得让 fast 先走一步或者用 do-while 结构。6.2 调试技巧与运行验证调试这个题最直接的办法是打印迭代路径。我常说任何和状态变换有关的题把状态链打印出来问题就一目了然。void debugPrint(int n) { int count 0; while (n ! 1 n ! 4 count 20) { printf(%d - , n); n getNext(n); count; } printf(%d\n, n); }用这个辅助函数分别跑 19 和 2能清楚看到 19 是怎么走到 1 的2 是怎么进入 4 循环的。这种可视化对理解循环检测非常有帮助。本地测试可以写一个简单的 main 函数验证三个版本的输出是否一致int main() { printf(19: %d %d %d\n, isHappy_hash(19), isHappy_floyd(19), isHappy_math(19)); printf(2: %d %d %d\n, isHappy_hash(2), isHappy_floyd(2), isHappy_math(2)); return 0; }预期输出是19: 1 1 1 2: 0 0 0如果三个解法结果不一致优先检查 getNext 函数因为它是公共依赖。95% 的情况下问题出在 getNext 而不是判断逻辑上。还要提一个容易忽略的边界值1 本身。输入 1 时三种解法都应该返回 true。哈希表法一进来 getNext(1) 1直接返回 true快慢指针法 fast 初始就是 1不进循环返回 true数学法 while 条件不成立n 1 返回 true。这个用例虽然简单但能排查出一些逻辑漏洞。最后的实际操作体会我个人刷题的习惯是平时自己写用快慢指针因为空间最省代码也不复杂。但如果在需要给别人讲解的时候我会先用数组哈希法把“为什么循环会被检测到”讲清楚再引入快慢指针。这个顺序不是在绕圈子而是顺着人的直觉走先记录状态再优化成指针追逐。有一次我在做一个数据处理的小工具需要判断一条配置链是否会发生循环回环当时第一反应就是拿快慢指针来检测比维护一张访问过的节点表简单太多而且性能完全够用。快乐数这道题表面上是数学题实际上是循环检测的通用思想。它把这些经典方法藏在一个看似平凡的小题里值得反复咀嚼。如果你把三种解法都能不看题解写出来那对哈希表的应用、链表判环的抽象、有限状态空间的分析都会有一个很扎实的底子。 
长河君 · 2026/10/18 14:17:57 · 阅读 1.2k C语言解LeetCode快乐数：哈希表、快慢指针与数学规律三种解法
刷 LeetCode 的人应该都见过 202 这道题——快乐数。第一次看到题目描述的时候我的第一反应是这有什么难的把每一位拆出来平方累加最后等于 1 就返回 true 呗。可等我真正动手写代码才发现自己还是天真了——如果这个数不是快乐数它会无限循环下去你怎么知道该什么时候停下来这题的真正考点根本不是如何计算平方和而是如何用一个可证明的终止条件来结束迭代。这篇文章我用 C 语言把三种主流解法都实现了一遍哈希表记录法、快慢指针法、数学规律法。三种解法的思路完全不同但都能在有限步内给出确定答案。无论你是刚开始刷题的初学者还是准备面试想系统性过一遍哈希和链表专题的开发者把这一题吃透都不亏。代码可以直接抄但背后的循环检测思想才是这题真正值钱的地方。1. 题目拆解快乐数到底在考什么1.1 从题目描述到核心考点先过一遍题目定义对于一个正整数每一次将该数替换为它每个位置上的数字的平方和然后重复这个过程直到这个数变为 1也可能无限循环但始终变不到 1。如果能变为 1那么这个数就是快乐数。举两个例子感受一下差异。19 是快乐数1² 9² 828² 2² 686² 8² 1001² 0² 0² 1到 1 了结束返回 true。2 不是快乐数2² 44² 161² 6² 373² 7² 585² 8² 898² 9² 1451² 4² 5² 424² 2² 202² 4注意看从 4 开始转了一圈又回到 4形成闭环。之后无论怎么迭代都只会在 4、16、37、58、89、145、42、20 这几个数之间打转永远到不了 1。所以这个题的核心考点就三个第一你能不能在第一次接触时意识到这里有循环。很多人上来就写while(n ! 1) n getNext(n)对快乐数没问题但遇到 2 这种数就直接死循环。严格说实现层面少了终止条件逻辑层面少了“循环检测”这个意识。第二你会不会选择合适的数据结构来检测循环。最自然的是哈希表把见到的数字存起来重复即循环。C 语言没有内置 HashSet怎么用数组模拟怎么分析数据范围这就是基本功。第三你懂不懂 Floyd 判圈算法。把数字变换抽象成链表快乐数问题就变成了链表判环问题。这是面试官非常喜欢的“场景转换”能力。1.2 为什么 C 语言解这题有特殊性网上很多题解用 Python 或 Java自带 Set 接口直接往集合里丢数就行几行代码搞定。但 C 语言不一样没有现成的哈希表你必须自己决定用什么结构。这个决定本身就在考察你对问题规模的理解。这里有一个非常关键的性质对于 32 位 int 范围内的数最多只有 10 位数字每一位最大是 9所以任意一个数的各位平方和最大不会超过 9² × 10 810。也就是说不管初始值多大只要执行一次 getNext 操作得到的中间结果一定落在 0 到 810 之间。这个性质直接简化了两个问题用数组模拟哈希表时数组只需要开 1000 左右不需要真正的哈希函数和冲突处理。因为中间结果被限制在这么小的范围里整个迭代序列必然快速进入两种状态之一要么到 1要么进入 4 那个循环。这也从侧面说明了为什么哈希表和快慢指针都能在有限步内结束。很多 C 语言的题解喜欢开一个很大的数组比如 10001其实没必要分析清楚数据范围能省不少内存也更体现水平。2. 解法一哈希表记录法2.1 思路与哈希表选型思路很直接把每次计算得到的中间值记下来如果发现某个值已经出现过说明序列进入了循环。因为数字变换的下一个值是唯一确定的一旦出现重复后面就会无限重复同一段序列。如果这个重复发生之前还没到 1那这个数就永远不可能变成 1。这个逻辑相当于在一条“状态链”上找重复节点。关键问题是用什么结构记录已经出现过的数字在 C 语言里最简单高效的方案是用布尔数组模拟哈希表bool seen[1000] { false };为什么数组大小为 1000 就够前面算过int 范围内任何数经过一次变换后结果最大不超过 810。因此每次迭代产生的 n 都是一个小于 1000 的数直接用 n 作为数组下标就能完成“查询是否见过”和“标记已见”两个操作。这种方式其实是“直接寻址哈希”因为关键字范围小且确定不需要设计哈希函数。这也是哈希表的一种特例面试时如果被问到可以大方地说出来比笼统地说一句“用哈希表”得分高。另一个小细节数组哈希表里的每一个位置只有两种状态见过或没见过所以用bool数组就够了不需要计数。如果误用了int数组也是可以的但没必要多占内存。这也是 C 语言里值得注意的思维习惯。2.2 C 语言实现与边界处理完整代码如下#include stdio.h #include stdbool.h int getNext(int n) { int sum 0; while (n 0) { int d n % 10; sum d * d; n / 10; } return sum; } bool isHappy_hash(int n) { bool seen[1000] { false }; while (1) { n getNext(n); if (n 1) { return true; } if (seen[n]) { return false; } seen[n] true; } }这里有一个非常容易踩的坑必须先执行n getNext(n)再去访问seen[n]。如果你直接写成if (seen[n])而初始 n 是一个很大的数比如 2147483647那数组就越界了程序行为未定义。这在 LeetCode 上可能表现为随机报错或答案错误在本地可能表现为段错误。说说这段代码的执行流程。进入循环后先把当前数变换到下一状态。如果下一状态是 1直接返回 true。如果已经见过这个状态说明前面走过这条路形成了环返回 false。否则把这个状态标记为已见继续循环。为什么这个循环一定会终止因为每次迭代后 n 都落在 0 到 810 之间而布尔数组大小是 1000最多只能标记 1000 个不重复的状态。抛开到 1 的情况如果一直重复不了那最多 1000 次迭代后必然出现重复状态。所以时间复杂度上界是有保证的。实测下来这个解法的时间表现非常稳定。因为实际迭代次数远小于 1000大多数数字在几十步内就出结果了。空间上固定大小数组可以认为是 O(1)。3. 解法二快慢指针Floyd 判圈3.1 把数字变换看成链表如果你刷过链表判环的题目看到快乐数会觉得特别眼熟。我们可以把每一次数字变换看成链表上的next指针跳转n的下一个节点就是getNext(n)。举个例子对于 2状态链是2 → 4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4 → 16 → ...这个序列进入了一个环等价于链表有环。对于 19状态链是19 → 82 → 68 → 100 → 1 → 1 → 1 → ...进入了一个自循环的“1”节点等价于链表遇到了一个特殊节点。所以判断一个数是不是快乐数就变成了判断这条“虚拟链表”是否有环以及环中是否有 1。Floyd 判圈算法正好解决这个问题。Floyd 判圈的核心思想是用两个指针慢指针每次走一步快指针每次走两步。如果有环快指针最终会追上慢指针两者相等如果无环快指针会先到达终点。对应到快乐数里终点就是 1。因为getNext(1) 1所以快指针会在 1 的位置上原地打转。只要快指针变成 1就可以直接判定是快乐数。为什么快慢指针一定会相遇可以这样理解当慢指针进入环之后快指针一定已经在环里了。此时快指针相对慢指针每次移动一步相当于在环形跑道上每轮追逐缩小一步距离。环的长度有限所以迟早会追上。3.2 完整实现与充分性分析C 语言代码如下bool isHappy_floyd(int n) { int slow n; int fast getNext(n); while (fast ! 1 slow ! fast) { slow getNext(slow); fast getNext(getNext(fast)); } return fast 1; }这里的初始化有个小讲究slow从 n 出发fast先走一步从getNext(n)出发。这样做的原因是如果不让快指针先走一步那么循环条件slow ! fast在第一次判断时就不成立循环直接退出程序会错误地把所有数都判为快乐数。这是初学 Floyd 判圈最容易犯的错。循环体内慢指针走一步快指针走两步。我用了嵌套的getNext也就是fast连续变换两次。可能有人会担心如果fast已经变成 1 了再调用getNext会不会出现问题不会因为getNext(1) 1它会一直停在 1不会越界也不会变成负数。循环退出的条件有两个要么快指针碰到 1说明是快乐数要么快慢指针相等说明检测到环不是快乐数。这里还有一种情况慢指针先到 1快指针还没到 1。慢指针到 1 后也会原地打转等快指针追上它此时slow fast但两者的值都是 1所以fast 1为 true返回结果依然正确。因此不需要单独判断 slow 是否为 1。时间复杂度上每次迭代仍然是执行若干次getNext每个节点的计算成本是 O(log n)迭代次数有限总体很快。空间上只用了两个整数变量是严格的 O(1)比哈希表解法更省内存。4. 解法三数学规律法4.1 唯一循环的发现与证明思路这个解法知道的人不多但一旦知道就会觉得这题原来可以这么简单。数学上已经证明在快乐数的迭代过程中除了 1 之外有且只有一个非 1 的循环4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4所有不是快乐数的数迭代若干次后一定会进入这个循环没有别的可能性。这个结论是怎么来的思路大致是因为任意数经过一次变换后都落到 0 到 810 之间所以整个状态空间有限。在这个有限集合上可以用穷举或反证的方式证明最终只会收敛到 1或者进入上面那一个环。面试时你不一定需要严格证明但最好能口头解释清楚“为什么可以这样判断”而不是直接背结论。一旦接受了这个结论代码就可以写得非常短只需要不断迭代如果中途变成 1返回 true如果中途变成 4返回 false。因为 4 是唯一循环的入口之一一旦落到 4后面必然在循环里打转永远到不了 1。为什么判断 4 就够了而不是把 16、37 这些数都列出来因为 16 继续算会变成 3737 会变成 58最后都会回到 4。所以哪怕当前值是循环里的其他数继续迭代下去也总会遇到 4。用一个等价的判断就可以覆盖整个循环。4.2 最短实现代码bool isHappy_math(int n) { while (n ! 1 n ! 4) { n getNext(n); } return n 1; }看到这段代码很多人会愣一下因为实在是太短了。循环条件写成n ! 1 n ! 4意思是只要没到 1 也没到 4就一直算下去。退出循环后如果 n 是 1说明是快乐数如果 n 是 4说明进入了坏循环。这里有一个边界情况要提醒如果入参是 0这段代码会陷入死循环因为getNext(0) 0而 0 既不等于 1 也不等于 4会一直在循环里出不来。不过题目明确说了输入是正整数所以 0 不在考虑范围内。如果想让代码更健壮可以加一个if (n 0) return false;的判断。从工程角度说这个解法的时间复杂度也是 O(log n) 级别的迭代次数空间 O(1)。代码量最小运行速度最快。但它依赖数学结论面试时如果只写这一版建议把前面两种解法的思路也准备好避免被追问时答不上来。5. 三种解法对比与面试推进策略5.1 复杂度与适用场景对照三种解法放在一起对比差异很清晰解法时间复杂度空间复杂度代码量直观程度适用场景哈希表记录法有限迭代约几十次O(1)固定数组中高教学首选最容易讲清楚快慢指针法有限迭代约几十次O(1)中中面试重点空间最优数学规律法有限迭代约几十次O(1)短低竞赛技巧加分项时间复杂度和迭代次数可以进一步解释。由于中间结果被限制在 0 到 810 之间哈希表法最多迭代 1000 多次就一定会有重复快慢指针法也必然在有限步内相遇或碰到 1。实际跑起来绝大多数数字在 20 步以内就出结果了。有人会提到 O(log n)严格来说这里的 n 是输入数字每一位的平方和计算需要 O(log n) 时间但迭代次数本身与 n 的关系不大分析复杂度时不要混淆。空间复杂度这块哈希表法如果用布尔数组是固定大小严格说 O(1)如果从抽象的“集合”角度看集合中最多存储所有中间状态数量有上界也是常数。快慢指针和数学法都是 O(1)。实际项目里遇到类似的状态循环检测问题比如配置文件的循环引用、协议解析中的状态机回环快慢指针这套思路都能直接迁移。我见过有人在数据流处理中用类似思路检测重复模式比维护一张大哈希表省很多内存。5.2 面试时怎么循序渐进地讲如果是在面试场景里我的建议是分三层递进。第一层先讲哈希表记录法。这是最自然的思路把见过的状态存下来出现重复就停止。面试官最想看到的是你能分析出中间结果的范围并且能具体到“数组开多大”这个细节这比空泛地说“用 unordered_set”要有力得多。第二层面试官大概率会问“能不能优化空间”。这时候引出快慢指针把数字变换类比成链表说明你懂 Floyd 判圈。这里要主动讲清楚为什么快慢指针一定会相遇以及初始值为什么要让 fast 先走一步。第三层作为加分项可以提数学规律法。先写出唯一的循环再给一个两行代码的解法。面试官一般会眼前一亮因为这展示了你对题目更深层的理解。但要注意数学法最好放在最后讲并且把前两种思路讲透否则容易显得像背题。如果面试官继续追问数学法的正确性可以这样回答任意数变换一次后都会落到 810 以内这个有限状态空间里只有 1 和那个已知循环两个吸引子这是可以穷举验证的结论。不需要把完整证明背出来但要表现出你理解这个结论的来源而不是死记硬背。6. 常见问题与避坑实录6.1 高频报错与逻辑问题这个题代码看起来短实际写起来容易出问题的地方不少我整理了一下。第一个经典错误是死循环。很多新手直接写while (n ! 1) { n getNext(n); }输入 2 就直接卡死。原因就是没有处理非快乐数的循环情况。这个错误几乎每个人都犯过我自己第一次写也栽在这里醒来之后才意识到这不是计算问题而是缺少终止条件。第二个经典错误是数组越界。哈希表法里如果写成seen[n] true; n getNext(n);顺序反了而且 n 初始是一个很大的数直接访问seen[2147483647]越界。第三个问题是 getNext 函数本身写错。常见的错误是把取余和除法顺序搞反。正确的写法是先d n % 10计算平方再n / 10。如果你先除再取余会漏掉或者重复处理某一位。另外注意sum d * d这里不要写成sum d * 2这种笔误很隐蔽输出结果会莫名奇妙的。第四个问题是快慢指针初始值。如果写成int slow n; int fast n; while (slow ! fast) { ... }循环一次都不会进去直接返回 true错得离谱。记得让 fast 先走一步或者用 do-while 结构。6.2 调试技巧与运行验证调试这个题最直接的办法是打印迭代路径。我常说任何和状态变换有关的题把状态链打印出来问题就一目了然。void debugPrint(int n) { int count 0; while (n ! 1 n ! 4 count 20) { printf(%d - , n); n getNext(n); count; } printf(%d\n, n); }用这个辅助函数分别跑 19 和 2能清楚看到 19 是怎么走到 1 的2 是怎么进入 4 循环的。这种可视化对理解循环检测非常有帮助。本地测试可以写一个简单的 main 函数验证三个版本的输出是否一致int main() { printf(19: %d %d %d\n, isHappy_hash(19), isHappy_floyd(19), isHappy_math(19)); printf(2: %d %d %d\n, isHappy_hash(2), isHappy_floyd(2), isHappy_math(2)); return 0; }预期输出是19: 1 1 1 2: 0 0 0如果三个解法结果不一致优先检查 getNext 函数因为它是公共依赖。95% 的情况下问题出在 getNext 而不是判断逻辑上。还要提一个容易忽略的边界值1 本身。输入 1 时三种解法都应该返回 true。哈希表法一进来 getNext(1) 1直接返回 true快慢指针法 fast 初始就是 1不进循环返回 true数学法 while 条件不成立n 1 返回 true。这个用例虽然简单但能排查出一些逻辑漏洞。最后的实际操作体会我个人刷题的习惯是平时自己写用快慢指针因为空间最省代码也不复杂。但如果在需要给别人讲解的时候我会先用数组哈希法把“为什么循环会被检测到”讲清楚再引入快慢指针。这个顺序不是在绕圈子而是顺着人的直觉走先记录状态再优化成指针追逐。有一次我在做一个数据处理的小工具需要判断一条配置链是否会发生循环回环当时第一反应就是拿快慢指针来检测比维护一张访问过的节点表简单太多而且性能完全够用。快乐数这道题表面上是数学题实际上是循环检测的通用思想。它把这些经典方法藏在一个看似平凡的小题里值得反复咀嚼。如果你把三种解法都能不看题解写出来那对哈希表的应用、链表判环的抽象、有限状态空间的分析都会有一个很扎实的底子。