📃 题目描述

题目链接：202. 快乐数 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

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

「快乐数」定义为：

对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。

然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。

如果 可以变为 1，那么这个数就是快乐数。

如果 n 是快乐数就返回 true ；不是，则返回 false 。

示例 1：

输入：19
输出：true
解释：
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1

示例 2：

输入：n = 2
输出：false

🔔 解题思路

⭐ 解题的关键其实就一句话：如果某个结果重复出现过，那这个数就不可能是快乐数，因为既然它曾经出现过，现在出现过，那就代表它未来还会出现，这就是死循环，永远不可能收敛为 1，直接返回 false 即可。

那如何快速判断一个元素是否出现过？我们应该立马就想到哈希。显然这题是不需要用到 HashTable 的 key-value 键值对的，只需要使用 HashSet 存储下结果就行：

class Solution {
    public boolean isHappy(int n) {
        if (n <= 0) {
            return false;
        }

        Set<Integer> set = new HashSet<>();
        
        int sumOfSquares = 0;
        while (n != 1) {
            sumOfSquares = getSumOfSquares(n);
            // 如果这个sumOfSquares曾经出现过，说明已经陷入了无限循环了，立刻 return false
            if (set.contains(sumOfSquares)) {
                return false;
            }
            set.add(sumOfSquares);
            n = sumOfSquares;
        }

        return true;
    }

    /**
     * 获取 n 所有数字的平方和
     */
    private static int getSumOfSquares(int n) {
        int res = 0;
        while (n > 0) {
            // n 的最后一个数字
            int temp = n % 10;
            // 每个数字的平方和
            res += temp * temp;
            // 从后往前处理
            n = n / 10;
        }
        return res;
    }
}

💥 复杂度分析

• 空间复杂度：O(N)
• 时间复杂度：while (n != 1) 可以看作对这个 n 中出现的所有平方和进行遍历，其时间复杂度为 O(N)，然后，while 循环里面的 getSumOfSquares 方法，对一个数进行处理获取到它所有数字的平方和，时间复杂度为 O(N)，所以总的时间复杂度为 O(N^2)