202.快乐数

一、问题描述

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

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

示例：

输入：19
输出：true
解释：
1^2 + 9^2 = 82
8^2 + 2^2 = 68
6^2 + 8^2 = 100
1^2 + 0^2 + 0^2 = 1

二、方案一：哈希表法

1、思路

使用哈希表记录每次计算得到的平方和。如果某个平方和之前出现过，说明进入了循环，此时可以判断该数不是快乐数。如果平方和变为 1，则该数是快乐数。

2、代码实现

func isHappy(n int) bool {
    seen := make(map[int]bool)
    for n != 1 && !seen[n] {
        seen[n] = true
        n = nextNumber(n)
    }
    return n == 1
}
func nextNumber(n int) int {
    sum := 0
    for n > 0 {
        digit := n % 10
        sum += digit * digit
        n /= 10
    }
    return sum
}

3、复杂度分析

• 时间复杂度：O(logn)，其中 n 是输入的数字。因为每次迭代都会将数字减少一个或多个数量级。
• 空间复杂度：O(logn)，因为我们需要存储每次迭代的结果。

三、方案二：快慢指针法

1、思路

类似于检测链表中的循环，我们可以使用快慢指针的方法。慢指针每次移动一步，快指针每次移动两步。如果两者相遇，则说明存在循环，该数不是快乐数。如果快指针到达 1，则该数是快乐数。

2、代码实现

func isHappy(n int) bool {
    slow, fast := n, nextNumber(n)
    for fast != 1 && slow != fast {
        slow = nextNumber(slow)
        fast = nextNumber(nextNumber(fast))
    }
    return fast == 1
}
func nextNumber(n int) int {
    sum := 0
    for n > 0 {
        digit := n % 10
        sum += digit * digit
        n /= 10
    }
    return sum
}

3、复杂度分析

• 时间复杂度：O(logn)，与方案一相同。
• 空间复杂度：O(1)，因为我们只使用了几个变量来存储慢指针和快指针的值。

四、总结

方案	时间复杂度	空间复杂度	优点	缺点
哈希表法	O(logn)	O(logn)	实现简单	需要额外空间
快慢指针法	O(logn)	O(1)	空间效率高	实现稍微复杂
推荐使用快慢指针法，因为它在空间效率上更优。