202. 快乐数（Happy Number）

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

题目

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

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

示例：

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

思路

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

两种实现方式：

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

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

代码

// 快慢指针法
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 一开始就不成立
• getNext 中注意取每一位数字：n % 10 取最低位，n /= 10 去掉最低位，循环直到 n == 0
• 不要忘记判断 fast == 1 的情况——快指针可能提前到达 1

面试追问

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

关联题

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