非循环数（Happy Number）完整解题指南：平方和变换、哈希集合与环检测的 LeetCode 实战

非循环数（Happy Number）完整解题指南：平方和变换、哈希集合与环检测的 LeetCode 实战

【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode

本文以仓库 hints/non-cyclical-number.md 的提示文档为主线，系统讲解"非循环数"（即 LeetCode 202 Happy Number，快乐数）的数学模型、环检测思路与多语言实现。读者将掌握"各位数字平方和"变换函数的写法、用哈希集合检测重复数字的经典套路，以及如何用快慢指针把空间复杂度从O(logn)降到O(1)，并能在 Python、Java、C++、Go、Rust 等语言中直接落地。

问题背景：什么样的数才是"非循环数"

"非循环数"这个命名取自 NeetCode 系列对 LeetCode 202（Happy Number）的别称，核心定义如下：

对于一个正整数n，反复执行"将n替换为其每一位数字的平方和"这一操作。若经过若干次变换后能够到达1，则称该数为非循环数（快乐数）；否则它将陷入一个永无1出现的循环，即"非循环"判定失败。

看一个典型的成功示例（n = 19，该示例同样出现在仓库 cpp/0202-happy-number.cpp 的注释中）：

1² + 9² = 82 8² + 2² = 68 6² + 8² = 100 1² + 0² + 0² = 1 → 到达 1，判定为 true

再看一个失败示例（n = 2）：2 → 4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4，从4开始会无限重复同一序列，永远到不了1，判定为false。

题目要求返回布尔值：true表示该数经过平方和变换链最终抵达1，false表示它被困在某个不含1的循环里。

核心数学模型：平方和变换函数

无论采用哪种解法，第一步都是实现同一个变换函数：把整数按十进制拆成单个数字，对每个数字求平方后累加。这个函数在仓库各语言实现中通常命名为getNext、sumSquareDigits或sumOfSquare。

以 python/0202-happy-number.py 为例：

def sumSquareDigits(self, n): output = 0 while n: output += (n % 10) ** 2 n = n // 10 return output

实现要点：

• n % 10取出当前最低位数字，n // 10去掉最低位，循环直到n为 0；
• 由于只做整除和取模，无需字符串转换，性能最好；go/0202-happy-number.go 给出了另一种"先fmt.Sprint(n)转字符串再逐字符转数字"的写法，结果等价但常数开销更大，实战中推荐取模写法；
• 单次变换的时间复杂度为O(logn)：十进制数字个数约为log10(n)，n的位数随其规模对数增长，这与提示文档要求的O(logn)复杂度目标一致。

为什么必须做"环检测"

提示文档（hints/non-cyclical-number.md 的 Hint 1）明确指出：

模拟上述过程：如果到达1返回true。但一旦某个数字被处理超过一次，我们就会陷入循环（cycle）。

这正是本题的关键陷阱：平方和变换是一个确定性函数，从任意起点出发，后续序列完全由当前值决定。一旦某个值在序列中第二次出现，那么它后面的所有值都会重复出现，形成闭环——要么环中包含1（快乐数），要么环中不含1（非快乐数）。

数学上可以证明（这也是仓库中"静态检测"解法的依据）：十进制下平方和变换的序列，只要不是快乐数，最终必然进入唯一的一个循环

4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4

该循环在 javascript/0202-happy-number.js 中以cycles数组的形式被硬编码：

const cycles = [4, 16, 37, 58, 89, 145, 42, 20];

因此，算法的本质可以归纳为一句话：沿着变换链前进，要么命中1，要么检测到环（某个值重复出现）并返回false。剩余的问题只有一个——如何高效地"检测到环"。

解法一：哈希集合检测（提示文档的标准解法）

提示文档（Hint 2）给出了最直观的落地方案：

使用哈希集合（hash set）检测某个数是否已被处理。每一步用变换函数更新n：若结果为1返回true；若n已存在于集合中返回false；否则把n加入集合继续循环。

typescript/0202-happy-number.ts 几乎逐字实现了该逻辑：

function isHappy(n: number): boolean { const visit = new Set(); while (!visit.has(n)) { visit.add(n); n = sumOfSquares(n); if (n == 1) return true; } return false; }

java/0202-happy-number.java 采用同样的思路，并显式处理了边界值：

public boolean isHappy(int n) { if (n == 1 || n == -1) { return true; } Set<Integer> visit = new HashSet<Integer>(); while (!visit.contains(n)) { visit.add(n); n = sumOfSquare(n); if (n == 1) return true; } return false; }

go/0202-happy-number.go 用map[int]bool充当集合，并把"先判重再写入"的循环条件用for {}无限循环 +break表达，语义等价：

for { if seen := alreadySeen[n]; seen { break } alreadySeen[n] = true // ...计算平方和 total if total == 1 { return true } n = total total = 0 } return false

复杂度分析（与提示文档推荐一致）：

• 时间复杂度O(logn)：每次变换O(logn)，而数字值随变换快速收缩——例如任意 3 位数经一次变换后最大为9² × 3 = 243，之后序列被限制在很小的数值范围内，实际迭代次数是常数级；
• 空间复杂度O(logn)：哈希集合最多存放变换链上出现过的不同数值。

解法二：快慢指针（Floyd 环检测），空间降到 O(1)

哈希集合解法简单直观，但需要O(logn)额外空间。提示文档给出的"推荐复杂度"为O(logn)时间 +O(logn)空间，即哈希解法即可达标；不过若想进一步把空间压到O(1)，仓库中的多语言实现展示了经典技巧——快慢指针。

核心思路：慢指针每次走一步（变换一次），快指针每次走两步（变换两次）。若序列中存在环，快慢指针必然在环内相遇；若序列直达1，则快指针先到达1。相遇后只需检查当前位置是否为1即可判定。

python/0202-happy-number.py 的实现：

class Solution: def isHappy(self, n: int) -> bool: slow, fast = n, self.sumSquareDigits(n) while slow != fast: fast = self.sumSquareDigits(fast) fast = self.sumSquareDigits(fast) slow = self.sumSquareDigits(slow) return True if fast == 1 else False

cpp/0202-happy-number.cpp 的注释给出了相同的思路说明，并在循环条件中额外加入fast != 1提前退出：

class Solution { public: bool isHappy(int n) { int slow = n; int fast = getNext(n); while (slow != fast && fast != 1) { slow = getNext(slow); fast = getNext(getNext(fast)); } return fast == 1; } private: int getNext(int n) { int sum = 0; while (n > 0) { int digit = n % 10; n /= 10; sum += pow(digit, 2); } return sum; } };

c/0202-happy-number.c 与 kotlin/0202-happy-number.kt 的结构几乎一致，均以while (slow != fast)为外层循环、快指针内部嵌套两次变换：

class Solution { fun isHappy(n: Int): Boolean { var slow = n var fast = sumSquareDigits(n) while (slow != fast) { fast = sumSquareDigits(sumSquareDigits(fast)) slow = sumSquareDigits(slow) } return fast == 1 } // ... }

复杂度分析：时间仍为O(logn)（快慢指针只是把常数放大到约 2 倍，数量级不变）；空间降为O(1)，因为只用了两个整数变量，不依赖任何集合。

解法三：数学常数优化，利用唯一循环

由于非快乐数最终必然落入唯一循环4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4，可以把"环"的信息直接编码进代码，省去运行期建集合的开销，时间与空间均为O(logn)与O(1)。

变体 A：静态哈希集合。javascript/0202-happy-number.js 把已知循环的所有值预置进Set，循环条件只需判断n === 1 || seen.has(n)：

var isHappy = (n) => { const cycles = [4, 16, 37, 58, 89, 145, 42, 20]; const seen = new Set(cycles); while (!(n === 1 || seen.has(n))) { n = getNext(n); } return n === 1; };

变体 B：只判断n == 4。因为环上任何一个节点都通向4，所以只要序列中出现4即可判定为非快乐数。rust/0202-happy-number.rs 用 Rust 的match精准表达了这个判定：

impl Solution { pub fn is_happy(mut n: i32) -> bool { loop { let mut s = 0; while n > 0 { s += (n % 10).pow(2); n /= 10; } match s { 1 | 4 => break s == 1, _ => n = s, } } } }

这一变体同样出现在 javascript/0202-happy-number.js 的第三种实现中（const hasCycle = () => n === 1 || n === 4;）。注意这两种变体依赖"非快乐数必入 4-循环"的数学结论，属于领域知识优化；在面试中建议先给出解法一，再补充说明该优化，并指出其成立的前提是十进制平方和变换的这一性质。

三种解法复杂度总览

解法	检测环的手段	时间复杂度	空间复杂度	仓库代表实现
哈希集合	运行期动态记录已见值	O(logn)	O(logn)	typescript/0202-happy-number.ts、java/0202-happy-number.java、go/0202-happy-number.go
快慢指针	Floyd 龟兔赛跑，相遇即环	O(logn)	O(1)	python/0202-happy-number.py、cpp/0202-happy-number.cpp、c/0202-happy-number.c、kotlin/0202-happy-number.kt
数学常数	硬编码唯一循环 / 判定n == 4	O(logn)	O(1)	rust/0202-happy-number.rs、javascript/0202-happy-number.js

选择建议：提示文档要求的"不劣于O(logn)时间 +O(logn)空间"由解法一即可满足；追求极致空间或作为进阶展示时使用解法二；解法三适合在确认数学结论后作为常数级优化补充讲解。

多语言实现速查

本仓库在 12 种语言中均提供了本题实现，文件名统一为0202-happy-number，便于对照学习：

• Python：快慢指针
• Java：哈希集合 + 边界值处理
• C++：快慢指针 +pow
• C：快慢指针
• Go：map判重 + 字符串拆分写法
• TypeScript：哈希集合
• JavaScript：四种解法齐备，含静态环集合与n == 4判定
• Kotlin：快慢指针
• Rust：match匹配1 | 4，O(1)空间
• 此外仓库还包含 csharp、ruby、swift、dart、scala 等语言目录下的同名实现

对照阅读时建议重点关注两点：其一，getNext/sumSquareDigits在不同语言中"取模拆位"的写法差异（n // 10vsMath.floor(n / 10)vsn /= 10，整数除法语义各不相同）；其二，环检测的数据结构选型（Set、HashSet、map[int]bool在各自语言中的惯用法），这两点正是把同一算法移植到多语言时的常见踩坑点。

总结

非循环数（快乐数）题目本身逻辑简单，但它是"确定性变换 + 环检测"这类问题的典型代表，与链表判环、函数迭代找周期等问题共享同一套思维模型。完整解题链路为：先写出O(logn)的平方和变换函数；再用哈希集合检测重复（对应提示文档 Hint 1/2 的标准答案）；进阶时用快慢指针把空间降到O(1)；最后可以基于"非快乐数必入4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4唯一循环"的数学结论做常数级优化。掌握了这条链路，你就同时具备了快乐数问题本身、哈希判重、Floyd 环检测三类面试高频考点的实战能力。

【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode