企业官网建设流程全解析

LeetCode-Go 题解：202. Happy Number 快乐数判定与哈希表判环实现详解

【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go

本篇技术指南以 202. Happy Number 题解文档 为主体，结合 LeetCode-Go 仓库中的 Go 源码与单元测试，完整讲解"快乐数"（Happy Number）的定义、模拟运算流程、哈希表判环算法及其复杂度分析。读者学完后，不仅能独立实现该题的 Go 解法，还能掌握"用哈希集合检测迭代过程是否陷入循环"这一通用解题范式，可迁移到其他判环类问题（如链表中环、无限小数循环节等）。

题目描述

编写一个算法来判断一个数字是否为"快乐数"（happy number）。

快乐数定义为：从任意正整数开始，用其每一位数字的平方和替换该数，并重复这一过程，直到结果等于 1（此后保持为 1），或者陷入一个不包含 1 的无限循环。那些最终能够收敛到 1 的数，就是快乐数。

示例

Input: 19 Output: true Explanation: 1² + 9² = 82 8² + 2² = 68 6² + 8² = 100 1² + 0² + 0² = 1

从 19 出发，依次得到 82 → 68 → 100 → 1，最终收敛到 1，因此 19 是快乐数。

题目理解：把定义翻译成算法

"快乐数"的定义本质上描述了一个迭代函数：

f(n) = 每一位数字的平方之和

从任意正整数n开始反复应用f，会得到一条序列n, f(n), f(f(n)), ...。该序列的归宿只有两种可能：

1. 序列到达 1 并停留在 1（因为1² = 1）；
2. 序列进入一个不包含 1 的循环，永无止境。

因此，题目的判定逻辑可以简化为：反复计算各位数字平方和，若在某一步得到 1，返回true；若检测到之前出现过的数字（即形成循环），返回false。

解题思路：模拟迭代 + 哈希表判环

官方文档给出的核心思路只有一句话——"按照题意要求做即可"（Just follow the requirements of the problem statement），但其背后的关键决策点是如何判定循环。

因为该迭代过程是确定性的（同样的输入必然得到同样的输出），一旦某个数字在序列中第二次出现，后续就必然重复之前走过的路径，从而形成环。所以只需要用一个哈希表（Go 中为map）记录每一步已经访问过的数字，在每一步生成新数字后检查它是否已经存在于记录中：

• 若存在 → 说明陷入循环，且循环中不含 1，返回false；
• 若新数字是 1 → 循环条件n != 1不满足，退出循环，返回true。

这种思路不需要任何数学推导或快慢指针，是"模拟 + 记忆化"的最直观实现，也正是本仓库题解所采用的方式。

Go 源码实现解析

仓库中的核心实现位于 202. Happy Number.go，由两个函数组成：

package leetcode func isHappy(n int) bool { record := map[int]int{} for n != 1 { record[n] = n n = getSquareOfDigits(n) for _, previous := range record { if n == previous { return false } } } return true } func getSquareOfDigits(n int) int { squareOfDigits := 0 temporary := n for temporary != 0 { remainder := temporary % 10 squareOfDigits += remainder * remainder temporary /= 10 } return squareOfDigits }

主函数isHappy：模拟与判环

func isHappy(n int) bool { record := map[int]int{} for n != 1 { record[n] = n n = getSquareOfDigits(n) for _, previous := range record { if n == previous { return false } } } return true }

执行流程逐行拆解：

1. 初始化记录表：record := map[int]int{}用于记录所有已访问过的数字；
2. 循环终止条件：for n != 1——只要当前数字不是 1 就继续迭代；一旦得到 1，循环自然退出，函数返回true；
3. 记录当前数字：record[n] = n将本轮迭代的输入数字写入哈希表；
4. 计算下一步：n = getSquareOfDigits(n)求出当前数字的各位平方和，作为下一轮迭代的输入；
5. 循环检测：遍历record，若新得到的n曾经出现过，说明序列已经进入循环且永远无法到达 1，立即返回false。

需要说明的是，map[int]int{}在这里仅当作"集合"使用，value 值本身没有业务含义，用map[int]bool或map[int]struct{}在语义上更贴近"记录存在性"，读者可自行改写。

辅助函数getSquareOfDigits：拆位求平方和

func getSquareOfDigits(n int) int { squareOfDigits := 0 temporary := n for temporary != 0 { remainder := temporary % 10 squareOfDigits += remainder * remainder temporary /= 10 } return squareOfDigits }

该函数采用取模 + 整除的标准拆位手法：

• temporary % 10取出最低位数字；
• 累加该位数字的平方（remainder * remainder）；
• temporary /= 10去掉最低位，继续处理下一位；
• 直到temporary == 0，所有位处理完毕。

例如对n = 19：9² = 81、1² = 1，累加得82，与题目示例完全一致。注意此函数对n = 0时循环体不执行、返回 0，这在后续测试用例（如输入 0 不会出现，因为题目保证正整数）中无影响。

单元测试与验证

仓库为本题提供了完整的表格驱动测试，位于 202. Happy Number_test.go。测试覆盖了四种输入：

测试代码遵循本仓库统一的question202/para202/ans202结构组织用例，运行时输出格式为：

fmt.Printf("------------------------Leetcode Problem 202------------------------\n") for _, q := range qs { _, p := q.ans202, q.para202 fmt.Printf("【input】:%v 【output】:%v\n", p, isHappy(p.one)) }

执行验证方式（任选其一）：

# 方式一：运行该题所在的 leetcode 包的全部测试 go test ./leetcode/0202.Happy-Number/... # 方式二：仅运行本题测试 go test -run Test_Problem202 ./leetcode/0202.Happy-Number/... # 方式三：仓库提供的覆盖率脚本（生成 coverage.txt） ./gotest.sh

其中 gotest.sh 使用go test -covermode=atomic -coverprofile=coverage.txt ./leetcode/...对整个leetcode包批量生成覆盖率文件，这也是本仓库宣称 100% 测试覆盖的验证入口。可以推断，isHappy与getSquareOfDigits均被上述用例完全覆盖。

复杂度分析

时间复杂度：O(L)，其中L是序列进入循环（或到达 1）前的数字个数。虽然代码在每一轮迭代中遍历一次record（当前实现为 O(1) 查找循环被写成了 O(已记录数) 的遍历，实际运行时可简化为直接查哈希表），但关键在于：对任意正整数，各位平方和的最大值增长是受限的。例如 4 位数最大为 9999，其平方和为4 × 81 = 324；可以证明，数字一旦超过 243，下一步的平方和必然回落。因此序列中可能出现的不同数字非常有限（远小于 1000），循环必然在有限步内被检测到，整体可以视为常数级迭代次数。

空间复杂度：O(L)，record哈希表存储了序列中出现的所有不同数字。若改用后面提到的快慢指针法，空间复杂度可降为 O(1)。

深入扩展：数学性质与更优实现

为什么非快乐数必然陷入循环

这是本题判定"循环即失败"的数学依据。对任意k位数，其各位平方和的最大值为81k。当k ≥ 4时，81k < 10^(k-1)（例如 4 位数最大平方和 324 远小于最小的 4 位数 1000），说明足够大的数经过一次变换后位数必然减少。因此序列中的数字被限制在一个有界范围内，由鸽巢原理可知，重复出现必然发生，即必然进入循环。这就是"循环中不含 1 即为非快乐数"这一判据成立的根本原因。

快慢指针（Floyd 判环）优化空间

由于迭代函数是确定性的，快乐数判定本质上是"单链表是否带环"问题：把每个数字看作链表节点，getSquareOfDigits就是next指针。因此可以直接套用 Floyd 快慢指针算法，将空间复杂度从 O(L) 降为 O(1)：

func isHappyFloyd(n int) bool { slow, fast := n, n for { slow = getSquareOfDigits(slow) fast = getSquareOfDigits(getSquareOfDigits(fast)) if fast == 1 { return true } if slow == fast { return false } } }

快指针每次走两步，慢指针每次走一步；若二者相遇说明有环（非快乐数），若快指针先到达 1 则为快乐数。

已知循环入口 4

从测试用例的轨迹可以看出，所有非快乐数最终都会进入4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4这个 8 元循环。因此也存在一种极简判据：迭代过程中一旦出现 4，即可断定不是快乐数。不过该判据属于经验结论，需要数学证明支撑，作为工程实践中的快速剪枝技巧了解即可，教学上仍推荐通用的哈希表或快慢指针方案。

总结

本文以 关联题解文档 为骨架，完整还原了题目定义、示例推演与 Go 实现，并补充了源码逐行解析、测试验证、复杂度推导与判环优化。快乐数问题虽小，却是理解"确定性迭代 + 哈希记忆化"思想的经典入门题，这一模式在后续许多判环、去重类问题中都会反复出现，值得牢固掌握。

【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go