202. 快乐数（Happy Number）¶

频次 ★★★ · 难度 🟢 · 高频：全厂

题目¶

编写一个算法判断一个数 n 是不是快乐数。

快乐数定义为：对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和，然后重复这个过程，直到这个数变为 1，也可能无限循环但始终变不到 1。如果可以变为 1，那么这个数就是快乐数。

示例：

输入: n = 19
输出: true
解释:
1² + 9² = 82
8² + 2² = 68
6² + 8² = 100
1² + 0² + 0² = 1

思路¶

核心问题是检测循环——如果计算过程中出现重复的数字，说明进入了循环，永远不可能到 1。

两种实现方式：

HashSet 记录：用 HashSet 存储每次计算的结果，如果新结果已在 Set 中出现，说明进入循环，返回 false；如果结果为 1，返回 true。空间 O(log n)。
快慢指针：将每次计算看作链表的"next"指针，用快慢指针检测环——如果快慢指针相遇且值不为 1，说明有环（不是快乐数）；如果快指针到达 1，说明是快乐数。空间 O(1)。

推荐快慢指针法，空间更优，且体现与"环形链表"的解题思路迁移。

两种循环模板别搞混（用户实际踩过的坑）：

141/142 的写法是「先移动、后比较」，比较在循环体里，所以初始 slow = fast = head 没问题：

while (fast != null && fast.next != null) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow == fast) return true;
}

202 的快慢指针写法是「先比较、后移动」，比较在循环条件里，所以两个指针必须先错开：

int slow = n;
int fast = getNext(n);              // 先走一步错开
while (fast != 1 && slow != fast) {  // 先比较
    slow = getNext(slow);            // 后移动
    fast = getNext(getNext(fast));
}

如果 202 里 fast 也从 n 开始：slow != fast 初始就是 false，循环一次都不执行，直接返回 fast == 1 → 19、7 这类快乐数会被误判为 false。

代码¶

// 快慢指针法
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;
}

private int getNext(int n) {
    int sum = 0;
    while (n > 0) {
        int digit = n % 10;
        sum += digit * digit;
        n /= 10;
    }
    return sum;
}

// HashSet 法（更直观，空间 O(log n)）
public boolean isHappy(int n) {
    Set<Integer> seen = new HashSet<>();
    while (n != 1 && !seen.contains(n)) {
        seen.add(n);
        n = getNext(n);
    }
    return n == 1;
}

复杂度¶

时间：O(log n) — 每次 getNext 需要 O(log n) 时间（数字位数），循环次数有上限（对于 int 范围，1 的平方和或进入循环的步数是常数级）
空间：快慢指针 O(1)；HashSet 法 O(log n)

边界条件¶

n = 1：直接返回 true，1² = 1，是快乐数
非快乐数一定进入循环：已知非快乐数最终会进入 4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4 的循环，不可能无限增长
大数：getNext 按位计算，不受 int 范围影响；最大三位数 999 的平方和为 243，所以计算过程中数字会快速缩小

变式¶

只用一个 HashSet 的早期退出：在循环中检查 n == 1 或 seen.contains(n)，哪个先成立就对应哪种结果
数学法：已知唯一的循环是 4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4，可以硬编码这个循环，但面试中不推荐——面试官想看的是"检测循环"的通用思维

易错点¶

快慢指针法中，fast 初始值要调用一次 getNext(n)，不能和 slow 一样初始为 n——否则 while 条件 slow != fast 一开始就不成立，循环一次不执行，19、7 会被误判为 false
getNext 取各位数字用取余 + 整除（n % 10 / n /= 10），不要转 String：取余纯算术、O(1) 空间，转 String 多一次字符串分配和解析，常数更大（只在数字超出 int/long 范围时才考虑）
fast != 1 是提前退出优化，不是正确性必需：去掉后，快乐数的 slow、fast 最终都停在 1，slow == fast 也会打破循环，return fast == 1 仍然正确，只是多走几步才相遇
while 条件里 fast != 1 建议写在前面：快指针一旦踩到 1 就确定是快乐数，不用等 slow 追上来

面试追问¶

为什么非快乐数一定会进入循环？ 因为 getNext(n) 的结果有上界——对于 k 位数，最大平方和为 81k（9²×k），而 k 位数的最小值是 10^(k-1)。当 k 足够大时，平方和一定小于原数（如 1000 的平方和最大为 81×4=324），所以序列必然被限制在有限范围内，根据鸽巢原理一定会重复。
快慢指针法和 HashSet 法怎么选？ 快慢指针 O(1) 空间，适合面试展示"问题转化"能力（把数字变换看作链表 next）；HashSet 法更直观，适合快速实现。如果面试官追问空间优化，再给快慢指针。

关联题¶

同套路：141. 环形链表 —— 快慢指针检测循环的经典模板
知识点：快慢指针（Floyd 判圈算法）的核心思想——如果有环，快指针一定会在环内追上慢指针