0202.快乐数
难度：🟢 简单
标签：哈希表、数学、双指针
链接：202. 快乐数
题目描述
编写一个算法来判断一个数 n 是不是“快乐数”。
「快乐数」 定义为：
对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
如果这个过程 结果为 1，那么这个数就是快乐数。
如果 n 是 快乐数 就返回 true ；不是，则返回 false 。
示例 1：
输入：n = 19
输出：true
解释：
1² + 9² = 82
8² + 2² = 68
6² + 8² = 100
1² + 0² + 0² = 1
示例 2：
输入：n = 2
输出：false
解题思路
核心思想
本题的核心在于，一个数的“快乐数”变换过程最终只有两种结果：要么最终会变成 1，要么会进入一个不包含 1 的无限循环。因此，问题的关键就变成了如何检测这个“无限循环”。
思路选择
哈希集合法：这是最直观的思路。我们可以使用一个哈希集合（Set）来记录变换过程中出现过的所有数字。在每一次计算出新的数字后，我们都检查它是否已经存在于集合中。如果存在，说明我们进入了循环，该数不是快乐数。如果数字最终变成了 1，则它是快乐数。
快慢指针法：这是一个空间复杂度更优的巧妙思路。我们可以将数字的变换过程看作一个链表，每个数字是节点，下一个数字是
next指针。这样，判断是否存在循环就转化为了一个“环形链表”的判断问题。我们可以使用快慢指针，慢指针每次变换一次，快指针每次变换两次。如果存在循环，快慢指针终将相遇。如果相遇点是 1，则是快乐数；否则不是。
关键步骤 (哈希集合法)
初始化：创建一个哈希集合
seen，用于存储已经出现过的数字。定义辅助函数：创建一个辅助函数
getNext(num)，用于计算一个数各位数字的平方和。循环判断：启动一个
while循环，当n不等于 1 且n未在seen集合中出现过时，持续循环。 a. 在循环内部，将当前的n加入seen集合。 b. 调用辅助函数计算出下一个数，并将其赋值给n。返回结果：循环结束后，判断
n是否等于 1。如果等于 1，则为快乐数，返回true；否则说明进入了循环，返回false。
代码实现
// 辅助函数，命名清晰
var getCounted = function (n) {
let result = 0;
while (n !== 0) {
let square = n % 10;
result += (square * square);
n = Math.floor(n / 10);
}
return result;
}
/**
* @param {number} n
* @return {boolean}
*/
var isHappy = function (n) {
let set = new Set();
while (n !== 1) {
let count = getCounted(n);
// 判断逻辑正确
if (set.has(count)) return false;
set.add(count);
n = count;
}
return true;
};
复杂度分析
时间复杂度：O(log n) 一个数
n的下一个数最大不会超过(log₁₀n) * 9²，这是一个远小于n的数。因此，数字的大小会很快下降到一个较小的范围内，并且在这个范围内循环。所以时间复杂度可以认为是与log n相关的。空间复杂度：O(log n) 空间消耗主要来自哈希集合
seen，其存储的数字数量也与log n相关。
相关题目
总结
本题是哈希表和循环检测思想的经典应用。通过记录历史状态，可以有效地判断一个过程是否进入了无限循环。快慢指针法则提供了一种不需要额外空间的、更为精妙的替代方案，值得深入理解。