★ FEATURED ARTICLE 刷算法题的时候第一次看到“Java双指针”和“快乐数”这两个词摆在一起我第一反应是这名字起得挺有意思点进去一看才发现是一道用双指针优雅解决循环检测的经典题目。它的描述很简短——判断一个正整数是不是“快乐数”但真正动手写代码时能不能想到把数字的迭代序列当成一条链表能不能理解为什么快慢指针一定相遇才是这道题真正考察的东西。这篇文章我会从数学性质讲起沿着三种解法层层递进最后给出一份可以直接落地的 Java 实现以及几个我实际踩过的坑。适合刚开始刷算法题、准备技术面试或者想系统理解快慢指针思想的开发者参考。1. 先读懂题目快乐数的数学性质与循环陷阱1.1 题目到底在问什么先直接看定义对于一个正整数每一次把这个数替换为它每个位置数字的平方和然后重复这个过程。如果最终能变成 1这个数就是快乐数如果陷入了一个不包含 1 的无限循环那它就是不快乐数。举两个例子能马上感受到这个定义的味道。19 是快乐数因为 19 → 1²9²82 → 8²2²68 → 6²8²100 → 1²0²0²1到这里就结束了。而 2 不是快乐数因为 2 → 4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4你会发现它绕了一圈又回到了 4然后永远在这个环里打转永远到不了 1。所以这道题表面上在考“迭代”本质上考的是“检测循环”。你不需要关心这个迭代过程到底要走多少步只需要判断序列的终点到底是 1 还是一个死循环。1.2 为什么“不快乐”的数必然陷入循环有限值域推理我第一次看这道题的时候脑子里冒出一个疑问凭什么 2 一定进循环万一某个数迭代几千次之后突然变成 1 了呢这个疑问如果不解决写出来的代码心里是没底的。答案在于一个非常朴素的数学事实经过若干次平方和变换之后数字的位数会被压缩到一个很小的范围。设当前数有 k 位每一位最大是 9那么一次变换后的结果最大为 81k。当 k 达到 4 的时候81×4324而一个四位数的下限是 1000也就是说四位以上的数经过一次变换必然变成三位数以内。三位数以内的数比如 999它的一次变换结果是 9²9²9²243还是三位以内。所以不管初始数有多大经过有限次迭代以后序列里的所有值都会被压缩到 1 到 243 这个小区间里。这个结论的意义非常大。一个确定性迭代加上一个有限的状态空间根据鸽巢原理序列最终一定会出现重复。一旦某个数重复出现后面整个过程就封闭成了循环。所以不是“可能会循环”而是“必然循环”。快乐数的循环是一个长度为 1 的自环也就是 1 → 1 → 1不快乐数的循环是另一个不包含 1 的环。这道题的本质就是判断最终落到哪个环上。1.3 那个著名的坏循环既然提到不快乐数的循环就绕不开那个所有不快乐数最终都会进入的坏循环4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4这个 8 个数字组成的环在任何一本算法笔记里都值得单独记一笔。它最直接的用途是作为手算的快速判定如果你在推导过程中看到了 4、16、37 这串数字里的任何一个那这个数必然不快乐不用继续算了。后面我会再回到这个技巧上。理解了“必然循环”这个前提整个题目的解法就豁然开朗了既然序列一定会进入某个环我只需要设计一种方式去检测环的存在并判断这个环是不是 1。这是解开这道题的总钥匙。2. 方案选型三条思路的层层递进2.1 最朴素但不可靠的限制迭代次数开始写代码之前很多人最先想到的可能是我设一个计数器比如迭代 500 次如果还没到 1就返回 false。这个思路在工程上能跑在算法题里却是禁用的。原因很简单你凭什么选 500 这个数如果初始值是一个巨大的数字500 次迭代够不够收敛到 1反过来如果一个数确实需要 501 步才能变成 1你的判断就错了。虽说前面已经证明序列会很快被压缩到 243 以内但这是一种事后诸葛亮的说法你没有办法在代码里证明“迭代次数上限是多少”是对的。更关键的是在面试场景里一旦你写出这种基于经验的阈值方案面试官几乎一定会追问“你能证明这个阈值永远有效吗”。不能证明那这个方案就站不住脚。所以这个方案只配用来做一次性的本地验证不能作为正式解法提交。2.2 可接受的方案哈希集合记录历史状态顺着“必然循环”的思路最自然的检测方法是把每一步得到的数字都记录下来如果新的数字已经在历史集合里出现过说明进入循环了。这就是哈希集合方案核心逻辑异常简单public boolean isHappy(int n) { SetInteger seen new HashSet(); while (n ! 1 seen.add(n)) { n getNext(n); } return n 1; }这里有一个非常优雅的细节seen.add(n)这个方法返回的是 boolean。如果 n 之前已经存在add会返回 false循环条件里set.add(n)的短路判断会让循环立刻退出。最后只需要检查n 1就能区分快乐和不快乐因为退出循环只有两种情况要么 n 变成了 1要么 n 在集合里重复出现。这个方案的思路清晰、代码量极少是很多在线评测平台的标准答案之一。它唯一的问题在于空间复杂度最坏情况下需要在集合里存储整个迭代序列的历史值。尽管前面已经证明序列长度存在理论上限但很多人的第一版代码不会想得那么深空间上多少有点浪费。2.3 更优雅的方案把迭代序列看作链表判环升级的思路是这样的如果把“每次计算下一个平方和”看作链表里的“next 指针”那么从初始数字出发的整个迭代序列就是一条隐形的链表。快乐数对应的是以 1 结尾的链表更准确地说1 是一个自环节点因为 getNext(1) 1next 指向自己不快乐数对应的则是一个不包含 1 的环。检测链表有没有环最经典的方法是快慢指针它的正式名字叫 Floyd 判圈算法。让慢指针每次走一步快指针每次走两步如果链表没有环快指针会先走到头如果有环两个指针最终一定在环内相遇。把这个逻辑挪到数字序列上慢指针每次算一次平方和快指针每次算两次快乐的情况下快指针会先到达 1然后在 1 的自环里原地打转不快乐的情况下两个指针会在坏循环里相遇。一旦相遇就说明这个序列存在一个不包含 1 的环直接返回 false。这个方案的优势是彻底摆脱了哈希集合空间复杂度降到了常数级同时保留了“检测循环”的核心能力代码还非常短。这也是“Java双指针--快乐数问题”这个标题真正的灵魂所在。3. Java 实现与逐行解析3.1 核心工具方法计算各位平方和不管是哪种方案第一步都是实现“计算各位数字平方和”的工具方法。这个方法代码不多但它决定了整个迭代的效率也藏着几个容易出错的小细节。private int getNext(int n) { int totalSum 0; while (n 0) { int digit n % 10; n n / 10; totalSum digit * digit; } return totalSum; }这个循环的逻辑就是经典的拆位n % 10取出当前个位数字n / 10去掉个位然后不断重复直到 n 变成 0。这里有一个小建议不要贪图方便去调Math.pow(digit, 2)。Math.pow返回的是 double计算平方还得处理类型转换和精度问题性能也比直接乘法慢实在没有必要digit * digit一行就搞定了。另一个值得提醒的点是这里计算平方和时每一位数字最大是 99²81所以中间结果不会溢出。只要输入是int范围内的正整数totalSum的值就会被限制在 81×10 以内因为 int 最多 10 位完全不用担心溢出。如果你后续把这个方法扩展到long类型它也依然安全。3.2 双指针主逻辑的完整实现把工具方法准备好以后主逻辑就是快慢指针的经典三行式了。我直接给出完整实现这也是我在实际编码里最推荐的写法public boolean isHappy(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从原始数字开始fast比 slow 先走一步这样可以保证循环条件在一开始不会被误判。进入循环体后每轮 slow 前进一格fast 前进两格。循环退出的条件有两个一个是fast 1说明快指针已经到了终点数字是快乐的另一个是slow fast说明快慢指针在环里相遇数字不快乐。最后判断fast 1完全覆盖了这两种情况。这里没必要在循环里额外判断slow 1因为如果 slow 到了 1处于更“前方”的 fast 只会更早到达 1循环条件里的fast ! 1会自然退出代码保持精简就好。3.3 初始化顺序最容易踩的坑我见过不少人在快慢指针初始化这一步栽跟头。最典型的错误写法是这样的int slow n; int fast n; while (slow ! fast) { slow getNext(slow); fast getNext(getNext(fast)); } return false;看起来好像没什么问题但两个指针同时从同一个起点出发第一轮进入循环体之前slow ! fast这个条件就已经不成立了程序直接退出根本不会进入迭代最后返回 false。哪怕输入是 19 这种快乐数结果也是错的因为 fast 从一开始就和 slow 相等判环逻辑完全失效。正确的做法就是让 fast 先走一步也就是int fast getNext(n)。还有一种方式是用do-while结构先移动再判断这样两个指针也可以同时从 n 出发int slow n; int fast n; do { slow getNext(slow); fast getNext(getNext(fast)); } while (slow ! fast fast ! 1); return fast 1;这两种写法本质是一样的。我个人的习惯是前一种因为它把“快指针先出发”这个动作显式表达出来了读代码的人更容易理解为什么会有这一步。面试手写代码的时候这个细节非常加分。4. 复杂度分析与边界情况4.1 时间复杂度的真实上界到了复杂度分析这一步很多人直接背出“O(log n)”但真要问为什么未必说得清。计算一次的getNext方法需要遍历当前数字的所有位当前数字的位数大约为 log₁₀(n)所以单次迭代的时间是 O(log n)。现在的问题是总共要迭代多少次借助前面论证的有限值域结论任何输入在经过有限次迭代后序列值都会落到 1 到 243 这个区间里。也就是说慢指针追赶快指针的过程最多在 243 附近的范围内进行迭代次数有一个非常小的常数上界。两者相乘整个算法的时间复杂度可以记为 O(log n)而其中的常数因子小到在评测环境里可以忽略不计。从这个角度看这道题用快慢指针在时间上没有劣势空间上还白赚一个 O(1)。你可能会问那哈希集合方案呢它的迭代次数同样是常数上界单步计算也同样是 O(log n)所以时间复杂度和快慢指针是同一个量级的。两者的差距主要落在空间上。4.2 空间复杂度与两种方案对比哈希集合方案为什么会浪费空间因为它在最坏情况下需要保存整个迭代序列的历史值尽管序列长度有界但毕竟是一个长度接近 243 的 set 对象。快慢指针方案只用两个int变量无论输入多大额外空间恒定不变这才是真正的 O(1)。这里放一张对比表会更直观方案时间复杂度空间复杂度代码量核心优势固定迭代次数取决于阈值O(1)最少没有任何理论保证哈希集合O(log n)O(1)但实际可存约两百多历史值很短思路直观最容易写对快慢指针O(log n)O(1)很短无需额外空间概念优雅选型的建议也很简单如果目标仅仅是 AC 这道题哈希集合完全够用代码不容易出错如果你在准备面试或者想练习双指针这一类高级技巧快慢指针是更值得掌握的方案因为同样的思想在链表环检测、寻找重复数等题目里还会反复用到。4.3 边界输入与测试用例验证写完代码别急着提交先用几个边界值和自己手算的用例验证一下。我通常会在本地跑这几组测试public static void main(String[] args) { Solution solution new Solution(); System.out.println(solution.isHappy(1)); // true System.out.println(solution.isHappy(19)); // true System.out.println(solution.isHappy(7)); // true System.out.println(solution.isHappy(2)); // false System.out.println(solution.isHappy(4)); // false System.out.println(solution.isHappy(100)); // true }逐个核对1 本身就是 1返回 true19 的迭代链我们前面推过终点是 17 也是一个著名的快乐数7 → 49 → 97 → 130 → 10 → 12 和 4 都会进入坏循环100 直接变成 1是快乐数。这些用例覆盖了最小输入、快乐路径、坏循环路径能快速验证实现没有犯低级错误。有一个边界值值得单独提一下很多人会问 n 0 的时候怎么办。题目明确说是正整数所以 0 不在讨论范围内。但如果你的工具方法要复用最好在getNext里对 0 有明确的行为定义。按照现有写法getNext(0) 会返回 0如果某个调用方真的传了 0程序会卡在 0 的自环里。稳妥的做法是在主方法的入口加一个前置判断或者依赖题目约束不去理会它。5. 双指针思想的延伸战场5.1 链表环检测从数字序列到真正的链表快乐数这个题目最妙的地方在于把数字迭代硬生生地翻译成了链表结构而链表判环正是快慢指针的“主场”。很多在线评测平台里都有一道非常基础的链表题给定一个链表判断它是否有环。标准解法就是用两个指针遍历链表快指针每次两步慢指针每次一步如果两个指针相遇了那就说明链表存在环。这个解法和快乐数快慢指针在数学上使用的完全是同一个定理在一个有限状态系统里如果有环两个速度不同的遍历者终将相遇。理解了快乐数链表环检测的代码你甚至不需要背public boolean hasCycle(ListNode head) { ListNode slow head; ListNode fast head; while (fast ! null fast.next ! null) { slow slow.next; fast fast.next.next; if (slow fast) { return true; } } return false; }注意这里是先让两个指针同时出发因为链表的终点是 null不会出现“起点即相遇”的误判问题。和快乐数里 fast 先走一步的初始化策略略有不同但背后对“什么时候可以判断进入环”的理解是相通的。5.2 寻找重复数快慢指针的另一个经典应用还有一个更强的应用场景值得写进笔记在一个长度为 n1 的数组里所有数字都在 1 到 n 之间其中至少有一个重复数字要求找出这个重复数并且不能修改数组、只能用常量空间。最暴力的做法是双重循环时间复杂度 O(n²)好一点的做法是排序后比较相邻元素但会修改原数组哈希集合能做到 O(n)但空间 O(n)。快慢指针在这里可以做到时间 O(n)、空间 O(1)。做法是把数组的每个位置看成一个节点nums[i]当作指向下一个节点的指针。因为存在重复值这个隐式链表必然会形成一个环用快慢指针找到环的入口入口节点对应的值就是重复数。这道题我第一次看到的时候觉得很玄学后来想通了它本质上就是在用“数组下标到数组值的映射”构造一条链表重复值等价于两个不同的下标指向同一个值也就是链表出现了分支进而产生环。这和快乐数的序列判环是同一个套路只是输入形式从数字变成了数组。5.3 避免混淆快慢指针与对撞指针聊到双指针必须提醒一句算法题里的“双指针”不是一个单一技巧至少能分成两类。一类是快乐数、链表判环里用的快慢指针它们从同一个起点出发以不同的速度前进靠“速度差”制造相遇另一类是对撞指针也叫左右指针它们分别从数组的两端向中间移动主要用于有序数组的查找、回文判断、盛水容器这类问题。刷题的时候很容易把这两类混为一谈。比如有人看到“双指针”就条件反射想到 left 和 right 从两端夹逼结果在快乐数这种需要检测循环的题目上完全用不上。反过来在有序数组两数求和的问题里用快慢指针也会很别扭。区分的关键是看数据结构链表或者迭代序列这类“单行道结构”优先想快慢指针数组这类“可随机访问的顺序结构”优先想对撞指针。这个判断标准能帮你少走很多弯路。6. 实操经验与编码建议6.1 面试中如何一步步展示思路这道题在面试里经常出现但它不是那种让你背答案的题更像一道“考察思维过程”的题。我复盘过自己模拟面试的经历也帮朋友做过面试演练发现最受认可的答题节奏是这样的第一步先聊数学性质。你可以主动说出来任何数的迭代序列最终都会进入循环因为值域有限这是一个确定性过程。这句话一出来面试官就知道你理解了题目的底层逻辑而不是只背了答案。第二步从哈希集合方案讲起。先说最自然的思路记录所有出现过的数一旦重复就终止。这个方案足够正确代码也短可以作为兜底方案。第三步自然地引出优化方向。你说“如果希望把空间复杂度降到 O(1)可以把这个迭代过程看成链表用快慢指针检测环。”然后解释为什么快慢指针会相遇。到这一步面试官最想听的“为什么”已经交代清楚了剩下的就是手写代码。整个过程中最忌讳的是上来就甩出快慢指针代码然后说“就是这样”。那样看起来像是背题面试官反而会追问各种边界条件容易露馅。从朴素方案逐步优化到双指针展示的是分析能力这才是面试要的。6.2 可读性与代码风格代码风格这种东西刷题的时候容易被忽略但在实际团队协作里很能体现功底。以快乐数实现为例几个小点值得坚持。变量命名尽量用slow和fast不要用s和f。这个题的核心逻辑就在速度差异上名字一目了然能大大降低阅读负担。getNext这个方法名也起得足够直观比calc、compute这种含义模糊的命名好得多。注释应该写在“为什么”的地方而不是翻译代码。比如快指针的初始化语句旁边值得加一行注释快指针先走一步避免起点即相遇的误判。这种注释是给未来看代码的人看的也是给自己三个月后看的。另外如果一个方法只有几行尽量保持它在类里的位置清晰。getNext作为私有工具方法放在主方法后面或者单独成段都能让结构更清爽。6.3 快速手算判断的小技巧最后分享一个我实际用过的偷懒技巧纯手算不写代码的时候特别好用。推导一个数是否快乐时不需要完整走完整条链。只要你发现序列中出现了 4、16、37、58、89、145、42、20 这 8 个数里的任何一个就可以直接判定它不是一个快乐数因为这些数都在那个坏循环上。反过来只要出现了 1那肯定是快乐数。所以手算的时候我们的目标就变成了观察迭代链里会不会撞上坏循环或者 1。比如给我一个数 123我先算1²2²3²14接着 1²4²17然后 1²7²50再算 5²0²25继续 2²5²29再算 2²9²85继续 8²5²89。一看到 89我就能直接告诉你不快乐根本不用继续往下算了。这个技巧在跟别人口头讨论问题时非常方便能省掉一大半计算。我个人在刚接触这道题的时候其实第一时间写的是哈希集合方案因为直觉上觉得“记录出现过的数字”天经地义。后来看到快慢指针解法时第一反应是“这也能行”等真正理解了有限值域和循环检测的关系以后才恍然大悟。如果你现在也在练习双指针类的题目我建议不要满足于代码通过动手把迭代链画出来把 fast 为什么不会跳过 slow、为什么二者必然相遇这件事想透彻。想明白的那一刻比记住这道题本身的收益要大得多。
阅读完成 · 觉得有帮助？
