对于任意n，可能出现以下几种情况：
-
最终会得到 1。
-
最终会进入循环。
-
值会越来越大，最后接近无穷大。
对于第三种情况，我们可以简单的列举一下：
会发现，13位数字的数位平方和最大是1053，1053是一个4位数，而4位数的数位平方和最大是324（回退到3位数），而3位数的数位平方和最大是243，因此，最终，4位数及4位数以上的数字的数位平方和都会落到243以内，因此要循环检查，如果又访问到了之前访问过的数字，则进入循环。
对于 3 位数的数字，它不可能大于 243。这意味着它要么被困在 243 以下的循环内，要么跌到 1。4 位或 4 位以上的数字在每一步都会丢失一位，直到降到 3 位为止。所以我们知道，最坏的情况下，算法可能会在 243 以下的所有数字上循环，然后回到它已经到过的一个循环或者回到 1。但它不会无限期地进行下去，所以我们排除第三种选择。
class Solution {
public int getNext(int n) {
int next = 0;
int t = 0;
while (n != 0) {
t = n % 10;
n = n / 10;
next += t * t;
}
return next;
}
public boolean isHappy(int n) {
Set<Integer> set = new HashSet<>();
while (n != 1 && !set.contains(n)) {
set.add(n);
n = getNext(n);
}
return n == 1;
}
}
用集合解答这道题存在一定问题，因为题目限定n是int类型，用集合记录每次的计算结果来判断是否进入循环，这个集合可能大到无法存储。
因此使用快慢指针来实现循环判断。慢指针走一步，快指针走两步。
class Solution {
public int getNext(int n) {
int next = 0;
int t = 0;
while (n != 0) {
t = n % 10;
n = n / 10;
next += t * t;
}
return next;
}
public boolean isHappy(int n) {
int slow = n, fast = n;
do {
slow = getNext(slow);
fast = getNext(fast);
fast = getNext(fast);
} while (slow != fast);
return slow == 1;
}
}
