LeetCode快乐数题解：双指针快慢指针与Floyd判圈算法实战

刷LeetCode热题100的时候我卡在这道“快乐数”上纠结了很久。倒不是题目本身多难而是它放在双指针专题里第一眼看上去完全不像能用双指针解决的问题——既没有数组也没有链表就是一个数字在那里反复求平方和。直到我把这个过程在纸上画出来才反应过来这玩意本质上和链表判圈是同一个问题快慢指针照样能玩得转。这篇就把我的完整思路、代码实现和调试过程中踩过的坑都记录下来希望能帮到正在刷这道题的朋友。1. 题目理解与思路拆解1.1 快乐数的定义与题目本质先看题目本身对于一个正整数每一次把它替换为每个位置数字的平方和然后重复这个过程如果最终能变成1那这个数就是快乐数如果陷入无限循环始终变不到1就不是快乐数。比如191²9²828²2²686²8²1001²0²0²1所以19是快乐数。再比如22²44²161²6²373²7²585²8²898²9²1451²4²5²424²2²202²0²4你会发现又绕回了4形成一个循环所以2不是快乐数。这里要抓住一个关键点除了最终得到1的情况其他所有可能都不是无限增大而是必然落入一个循环。题目描述中说得很含蓄只说了“也可能是无限循环但始终变不到1”但很多初学者没深想会觉得万一这个数越变越大怎么办其实不会。我们可以简单论证一下对于任意一个不超过10位数的正整数每一位最大是9平方和最大也就是81×10810所以计算一次平方和后结果无论如何都不会超过810实际三位数以上的数会迅速掉到三位数以内。也就是说这个变化过程一定在有限范围内打转要么碰到1要么重复出现某个数而一旦重复就说明进入了循环。1.2 暴力思路为什么不行最直觉的解法当然是模拟用一个集合哈希表把所有出现过的数记下来每算出一个新的数就先看看集合里有没有。如果有说明循环了返回false如果算出来是1返回true。这个解法没有任何问题时间复杂度也不差LeetCode官方题解里也给出了这个方案。但既然这题被归到双指针专题就需要考虑能不能不借助额外的存储空间。哈希法的空间复杂度是O(log n)级别——因为数字变化范围有限实际上是一个常数级别的上限但理论分析上我们按位数来算。如果能把空间复杂度压到O(1)也就是只使用若干个变量而不使用集合这题就多了一个值得学习的维度。快慢指针恰好能做到这一点。2. 双指针解法的核心原理2.1 把数字变化过程看成链表我第一次看题解里说“把每个数看成一个节点平方和的结果就是它的next指针”时有种恍然大悟的感觉。比如19这个数可以把19看成链表头节点82是它的next68是82的next100是68的next1是100的next而1的next还是1。对于一个会循环的数比如2它的轨迹上会出现一个环4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4最后一个4又指回之前的4这就是一个典型的环形链表。到这里问题就完全转换成了“判断链表是否有环并且找到环的入口是否等于1”。具体到快乐数其实只需要判断是否有环即可——因为如果有环环里既可能有1也可能没有但需要特别注意如果某个数在计算过程中出现了1那1的下一个结果还是1相当于在1这个节点上自环。所以更准确的判断是快慢指针相遇时如果相遇点是1说明它被“困”在1这个自环里了是快乐数如果相遇点不是1说明掉进了别的死循环不是快乐数。2.2 快慢指针为什么能检测循环快慢指针检测循环的原理和跑步套圈是一个道理。两个人在圆形跑道上跑一个人速度快一个人速度慢只要跑道是环形的速度快的人迟早会追上速度慢的人两人相遇。但如果跑道是直线速度快的人会先跑到终点永远不会掉头回来追慢的人。写代码时慢指针每次走一步也就是计算一次平方和快指针每次走两步也就是连续计算两次平方和。如果存在循环快指针最终会在环里追上慢指针如果不存在循环也就是最终停在1快指针会先“到达”1然后每次算出来的结果还是1本质上也是在1这个节点上打转所以最终两个指针都会停在1也算是一种“相遇”。关键在于如果这是个快乐数快指针会比慢指针更早进入1的循环里然后在1的位置等慢指针所以两者相遇时位置必然是1。如果这不是快乐数两个指针都会掉进同一个非1的循环最终在环里的某个点相遇。因此循环结束的条件就是快指针追上慢指针然后检查相遇点是否为1即可。这里还有一个隐含的数学细节不管是不是快乐数整个过程最终都会进入循环区别只在循环里有没有1。这是快慢指针能直接判断的根本前提。3. 完整代码实现与逐步解析3.1 Python实现快慢指针法class Solution: def isHappy(self, n: int) - bool: def get_next(num: int) - int: total 0 while num 0: digit num % 10 total digit * digit num // 10 return total slow n fast get_next(n) while slow ! fast: slow get_next(slow) fast get_next(get_next(fast)) return slow 1这段代码短小精悍但每一个细节都有讲究。先看辅助函数get_next它的作用是算出一个数的各位平方和。实现逻辑不复杂循环取模得到最低位数字累加它的平方然后整除10去掉最低位直到num变成0。这里要注意的是先取模再整除顺序不能乱——我在初学阶段经常写成先整除后取模导致结果完全错误。再看主流程。slow初始化为n本身fast初始化为get_next(n)也就是让快指针先走一步。为什么要这样初始化因为快慢指针一开始不能在同一个位置否则while循环压根不会进入直接返回slow 1对于快乐数来说这碰巧是对的1的next还是1但对于非快乐数比如2slow2fast4此时slow ! fast循环正常进入如果slow和fast都初始化为n2循环条件直接不成立会返回2 1即False——碰巧也对了但数字更大时结果可能就没这么幸运了。为了避免这个逻辑漏洞标准做法是先走一步让两者错开。进入while循环后慢指针每次移动一步快指针每次移动两步直到两者相遇。注意fast get_next(get_next(fast))这里有两层调用代表连续算两次平方和也就是快指针走两步。循环结束后判断相遇点的值是否等于1。如果等于1说明快慢指针在1这个自环节点处相遇了是快乐数如果不等于1说明掉进了非1的循环里不是快乐数。这个判断准确无误吗这里有个边界情况需确认如果某个非快乐数它的循环里恰好包含1即某一步算出了1但1的下一个结果还是1所以一旦到1就会停住1之后不会再跳出去所以如果轨迹上碰到过1最终数字就会变成1固定下来那它就是快乐数。因此有1出现的轨迹不可能是“非快乐数循环”所以慢指针和快指针相遇于非1的节点必然意味着这个数整个过程永远没到过1。3.2 C实现与哈希法的对比用C写一遍加深理解class Solution { public: bool isHappy(int n) { auto getNext [](int num) { int total 0; while (num 0) { int digit num % 10; total digit * digit; num / 10; } return total; }; int slow n; int fast getNext(n); while (slow ! fast) { slow getNext(slow); fast getNext(getNext(fast)); } return slow 1; } };C的lambda表达式用在这里很合适代码结构和Python版本一一对应。再放一个哈希法的版本两者对比看class Solution: def isHappy(self, n: int) - bool: seen set() while n ! 1 and n not in seen: seen.add(n) n sum(int(d) ** 2 for d in str(n)) return n 1两套解法都能通过差异主要在空间复杂度上。哈希法需要一个集合记录出现过的所有数字在实际运行中这个集合的元素个数最多也就几百个因为数字被限制在一个很小的范围内但理论分析时会认为是O(log n)甚至更精确一点是O(位数)级别。快慢指针只用了两个变量空间复杂度严格O(1)这是它最大的优势。3.3 复杂度分析的完整推导先分析时间复杂度。这里比较微妙因为get_next函数每次要遍历数字的每一位所以一次计算的复杂度是O(log n)n代表当前数字log n代表位数。快慢指针需要走多少步由于数字被限制在小范围内实际上无论输入的n有多大最终进入循环的步数都有一个很小的上界。网上有人实际测试过对于int范围内的所有正整数最多不超过几十步就能检测出结果。所以严格来说时间复杂度和输入数字的位数有关可以认为是O(log n)量级但实际上因为循环长度极短运行起来非常快。空间复杂度上快慢指针法只用了常数个额外变量O(1)哈希法最坏情况下要存储循环出现过的所有数字理论上是O(log n)。感性地解释一下快慢指针法本质上是用“时间”换“空间”多跑了几步计算省掉了整个集合的存储。在很多实际场景下如果内存敏感这种空间O(1)的方案更有吸引力如果是比赛环境追求代码简洁明快哈希法也完全够用。4. 常见问题与调试心得4.1 快慢指针会不会错过循环入口有朋友可能会问快指针每次走两步会不会刚好“跳过”慢指针导致永远不相遇事实上不会。在环里快指针每走两步、慢指针走一步相当于快指针相对慢指针每次靠近一步因为两者的速度差是1步/轮不存在“跳过去”的情况。这个结论和链表判圈那道题完全一致。就算快指针某时刻在慢指针前面一格下一步快指针移动两格后会到慢指针后面一格再下一步就会相遇。相对速度是1不会出现跨越。4.2 平方和计算的两个经典错误第一个错误是get_next里对0的处理。有些同学会把while条件写成while num 1或者漏掉num等于0的情况导致循环提前退出。实际上while num 0这个条件已经把所有正整数位都处理完了不需要额外处理0。不过要注意如果函数外部传入0比如isHappy(0)那0不是正整数题目没要求处理可以忽略。第二个错误是取余和整除的顺序。正确的操作顺序是先digit num % 10取到最低位累加平方再num // 10去掉最低位。我见过有人写成先把num除以10再去模那就会漏掉个位的数字。还有一种写法是直接用字符串转换sum(int(c) ** 2 for c in str(n))Python这么写很简洁但在C里用字符串处理反而更麻烦而且性能不如直接取模。4.3 测试用例与边界情况刷题时养成一个好习惯提交前先在本地跑几个典型用例。这道题我建议至少测这几组isHappy(1) True循环直接不进入slow和fast初始分别是1和1fast get_next(1) 1所以slow fast成立跳出循环后判断slow 1返回True。isHappy(19) True这是题目给的示例可以手动推演一下确认快慢指针都能在1处相遇。isHappy(2) False前面推演过会陷入4的循环返回False。isHappy(7) True7²494²9²979²7²1301²3²0²101²0²1最终确实能到1而且步数比19还多容易误判。isHappy(1111111) 这种大数用来验证get_next对大数的处理是否正确。这种测试不是为了逻辑正确性逻辑一样主要是确认不会出现整数溢出——Python和C的int都能轻松装下中间结果因为平方和不会超过几百所以没有溢出风险。4.4 关于刷题顺序和专题训练的一点体会我是在刷LeetCode热题100的时候遇到这道双指针题的。刚开始不理解为什么把它归为双指针后来把链表判圈和这题放在一起对比才真正理解了“状态机循环检测”这一大类问题的通用解法模板。如果你也在按专题刷题建议把这几题放一起做环形链表、环形链表II、寻找重复数、快乐数。它们的内核都是Floyd判圈算法只是表现形式完全不同——有链表、有数组、有纯数字。把这四题对照着看你会形成一种条件反射看到“重复出现”“循环”“陷入死循环”等字眼第一反应就是能不能用快慢指针检测。另外一个心得是哈希法并不是“低级解法”。在面试中如果时间紧张先给出哈希法的版本并分析它的复杂度然后补充说“如果面试官要求优化空间可以用快慢指针把空间压到O(1)”这反而展示了你的知识深度。在实际刷题过程中我不建议一开始就追求最优解而是先保证能AC再思考能不能优化。很多题目的最优解都是建立在朴素解法的理解之上的跳过朴素解直接看最优解反而容易消化不良。最后再分享一个我踩过的坑有一版代码我把fast初始值写成了n而不是get_next(n)导致while循环的条件一开始就不成立直接返回slow 1而这个判断在n2时恰好返回False在n19时返回False——因为19 ! 1但19明明是快乐数。这种“碰巧能过一部分用例但逻辑不全对”的写法最危险因为LeetCode上有些测试用例恰好能过提交后会在某组数据上翻车。所以无论代码多简单一定要在纸上推演一遍完整流程确认所有分支都符合预期。