如何判断一个数是不是快乐数？（LeetCode 202）

简化版

快乐数：对一个正整数，反复把它替换为「各位数字的平方和」，如果最终变成 1 就是快乐数；如果陷入不含 1 的循环就不是。如 19 → 1²+9²=82 → 68 → 100 → 1，是快乐数。难点是如何检测「陷入循环」——因为不快乐的数会无限循环。两种方法：① 用 HashSet 记录出现过的数，重复出现说明成环；② 快慢指针（Floyd 判环），快指针走两步、慢指针走一步，相遇则有环。

详细版

解法一：HashSet 检测循环

boolean isHappy(int n) {
    Set<Integer> seen = new HashSet<>();
    while (n != 1 && !seen.contains(n)) {
        seen.add(n);
        n = next(n);           // 替换为各位平方和
    }
    return n == 1;             // 到 1 是快乐数，否则陷入循环
}
int next(int n) {
    int sum = 0;
    while (n > 0) {
        int d = n % 10;
        sum += d * d;
        n /= 10;
    }
    return sum;
}

解法二：快慢指针（O(1) 空间）

boolean isHappy(int n) {
    int slow = n, fast = next(n);
    while (fast != 1 && slow != fast) {
        slow = next(slow);         // 慢：走一步
        fast = next(next(fast));   // 快：走两步
    }
    return fast == 1;
}

核心：不断求「各位数字平方和」，判断是否到 1 或成环。
HashSet 法：见过的数再出现即成环，O(n) 空间。
快慢指针法：把「求下一个数」看成链表 next，Floyd 判环，O(1) 空间。
复杂度：时间约 O(log n) 每步、总步数有限；空间 HashSet O(n)、快慢指针 O(1)。

完整版教学

一、快乐数的定义与关键难点

快乐数的过程：不断用「各位数字的平方和」替换当前数。快乐数最终收敛到 1（然后 1 → 1 停留）；不快乐的数会进入一个不含 1 的循环（如 4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4 无限转圈）。

核心难点：怎么知道「永远到不了 1」？如果不做循环检测，不快乐的数会让程序死循环。所以本题本质是**「检测这个变换序列是否成环」**——和链表判环是同一类问题。

二、为什么一定会「到 1」或「成环」

为什么序列不会无限增大而是必然收敛到 1 或某个环？因为平方和变换会把大数迅速拉小：对任意 3 位数，各位平方和最大是 9²×3 = 243；对更大的数，平方和增长远慢于数本身。所以序列最终会落到一个较小的有限范围内（大致 1~243），在有限个数里反复变换——根据鸽巢原理，有限状态里无限变换必然重复，要么撞上 1、要么进入循环。这保证了两种解法都会终止。

三、解法一：HashSet 记录见过的数

最直观：用一个 HashSet 记录每个出现过的数。每步求平方和后：

若得到 1 → 快乐数，返回 true。
若这个数已经在 set 里（重复出现）→ 说明进入循环、永远到不了 1，返回 false。
否则加入 set 继续。

简单可靠，空间 O(n)（存储序列中出现的数，实际有限）。

四、解法二：快慢指针（Floyd 判环，O(1) 空间）

把「求下一个平方和」next(n) 看成链表的 next 指针——这个序列就是一条可能带环的「链表」。用 Floyd 快慢指针判环：

慢指针每次走一步（slow = next(slow)）。
快指针每次走两步（fast = next(next(fast))）。
若序列收敛到 1，快指针会先到 1（fast == 1 结束，返回 true）。
若序列成环，快慢指针会在环内相遇（slow == fast），此时 fast ≠ 1，返回 false。

这和「环形链表 II」是同一个 Floyd 判环技巧，空间 O(1)，是本题的最优解，也是面试想考的点——把数学变换转化为链表判环。

五、求各位平方和的写法

next(n)：循环 d = n % 10（取末位）、sum += d*d（平方累加）、n /= 10（去末位），直到 n == 0。这是数位分解的标准操作，和数字反转、数位统计同源。

对 n=0，循环不执行并返回 0，这使 next 函数在所有非负状态上都有定义。
每次必须先保存当前末位再去掉它，避免把更新后的 n 用错到本轮平方中。
d 的范围只有 0 到 9，单项平方最大 81，普通正整数的数位平方和不会在一次计算中溢出 int。

六、把数值迭代看成函数图

定义 f(x) 为各位平方和，每个数只有唯一后继，因此轨迹是一条最终进入环的链。对十进制 d 位数，下一值最多为 81d；即使初始 n 很大，执行一次后也进入很小的有限集合。有限集合上的确定性迭代必然到 1 或重复某个旧状态。

n=19
1²+9² = 82
8²+2² = 68
6²+8² = 100
1²+0²+0² = 1 -> 快乐数
非快乐数会进入环，例如 2->4->16->37->...->4
HashSet 检测重复，Floyd 检测快慢指针相遇

校验维度	本题必须保持的结论
循环/递推不变量	HashSet 保存此前所有状态；Floyd 中 slow 走一步、fast 走两步，二者始终位于同一函数轨迹。
边界条件	题目输入为正整数；求平方和时循环取十进制位，0 的下一状态仍为 0。
复杂度与代价	状态会落入常数大小集合，理论上可视为 O(log n) 预处理后常数迭代；Set 占状态空间，Floyd O(1) 空间。
自检方式	用最小输入、典型输入和触及边界的输入分别手推，结果应与定义一致。

这组推演的作用不是替代证明，而是把抽象规则落到每一步状态变化上。面试写完代码后，应主动指出不变量如何保证不漏解，以及边界为何不会越界或死循环。若手推结果与定义不一致，应先修正状态语义，而不是继续给代码打补丁。

七、面试现场如何验证这道题

数学题不能只凭样例相信公式，必须同时核对定义域、推导条件和定宽整数边界。本题应先复述这条不变量：HashSet 保存此前所有状态；Floyd 中 slow 走一步、fast 走两步，二者始终位于同一函数轨迹。只有代码的初始化、更新顺序和终止条件都维持它，样例通过才具有证明力。

典型路径从“n=19”开始手推，最后应得到“HashSet 检测重复，Floyd 检测快慢指针相遇”。
边界复核：题目输入为正整数；求平方和时循环取十进制位，0 的下一状态仍为 0。
代价复核：状态会落入常数大小集合，理论上可视为 O(log n) 预处理后常数迭代；Set 占状态空间，Floyd O(1) 空间。
用 0、1、最小合法值和最大合法值检查公式的定义域。
乘法、取绝对值或取负前先判断是否可能触及 Integer.MIN_VALUE 等不对称边界。
若算法依赖单调性、抵消或整除关系，要明确题设保证何时成立、何时必须额外验证。

最后要主动构造一个“少写一次循环、改变一个不等号或交换两行更新就会失败”的反例。能说清反例破坏了哪条不变量，比只报出复杂度更能证明真正掌握了算法。

记忆钩子：本题的代码可以压缩，但“HashSet 保存此前所有状态；Floyd 中 slow 走一步、fast 走两步，二者始终位于同一函数轨迹。”这条正确性主线不能省。

八、常见误区与追问

误区：看见数值下降就能断定最终到 1。 序列可能上升并进入非 1 环，必须显式检测重复或用判环。
误区：快慢指针只能用于链表。 任何每个状态有唯一后继的函数迭代都形成隐式链表，可用 Floyd。
误区：slow 与 fast 相遇就说明是快乐数。 还要判断相遇点是否为 1；它们也可能在非 1 环中相遇。
追问：为什么轨迹不会无限产生新大数？ d 位数映射后至多 81d，远小于大多数 d 位数，随后进入有限范围。
追问：Set 解法何时返回 false？ 当前状态已在集合中出现，说明之后会重复同一轨迹形成环。
追问：可以预先记住非快乐环吗？ 可以，十进制正整数的非快乐轨迹最终进入固定环，但判环写法更通用。

九、加强记忆

快乐数 = 反复求各位数字平方和，到 1 是快乐数、陷入不含 1 的循环则不是。关键是检测循环：① HashSet 记录见过的数，重复出现即成环（O(n) 空间）；② 快慢指针（Floyd 判环）——把 next(n)=各位平方和 当链表指针，慢走一步、快走两步，到 1 则快乐、相遇则成环（O(1) 空间，最优）。序列必然收敛或成环（平方和把大数拉进有限范围 + 鸽巢原理）。核心洞察：这是链表判环问题的数学变体。

简化版

详细版