数组与哈希简单2 种解法
#202快乐数
反复把整数替换为各位数字平方和，判断序列最终是否到达 1。
#哈希表#数学#快慢指针
解题主线
01
状态空间有限，序列要么到达 1，要么进入不含 1 的环。
解法 1：哈希集合判环
记录已经出现的状态；遇到 1 成功，重复状态说明进入环。
时间复杂度
O(log n)，状态很快收敛到常数范围
空间复杂度
O(log n)
java
import java.util.HashSet;
import java.util.Set;
final class Solution {
public boolean isHappy(int n) {
Set<Integer> seen = new HashSet<>();
while (n != 1 && seen.add(n)) n = next(n);
return n == 1;
}
private int next(int number) {
int sum = 0;
while (number > 0) {
int digit = number % 10;
sum += digit * digit;
number /= 10;
}
return sum;
}
}记录已经出现的状态；遇到 1 成功，重复状态说明进入环。
- 修复未使用输入且恒返回 true 的旧代码。
解法 2：Floyd 快慢指针
把数字变换看作链表后继函数；快指针每轮走两步，检测是否在 1 或环中相遇。
时间复杂度
O(log n)
空间复杂度
O(1)
java
final class Solution {
public boolean isHappy(int n) {
int slow = n;
int fast = next(n);
while (fast != 1 && slow != fast) {
slow = next(slow);
fast = next(next(fast));
}
return fast == 1;
}
private int next(int number) {
int sum = 0;
while (number > 0) {
int digit = number % 10;
sum += digit * digit;
number /= 10;
}
return sum;
}
}把数字变换看作链表后继函数；快指针每轮走两步，检测是否在 1 或环中相遇。
边界与易错点
- 旧实现从 res=0 开始迭代，完全没有使用输入 n，并且无条件返回 true。
- 集合写法应把 n 作为首个状态；Floyd 写法需同时检测 slow == fast 与 fast == 1。
整理来源
由旧仓库源码复核、去重并整理；展示代码已按 Java 21 语义修正明显问题。
easy/Q202_isHappyNum.java