教程文档【免费下载链接】LogicStack-LeetCode公众号「宫水三叶的刷题日记」刷穿 LeetCode 系列文章源码项目地址https://gitcode.com/gh_mirrors/lo/LogicStack-LeetCode点击查看免费下载本篇是「宫水三叶的刷题日记」刷穿 LeetCode 系列第 No.507 篇的深度解读。文章以 LeetCode/501-510/507. 完美数简单.md 为核心骨架完整继承原题解中的数学推导、成对因子枚举思路与 Java 参考代码并结合本仓库的 Tag 归类体系补充边界情形论证、溢出规避原理与数论背景帮助你彻底掌握这一类「因数统计类」简单题的通用解法读完后可直接在 LeetCode 上独立 AC 并迁移到其他因子枚举类题目。题目描述与输入输出约定对于一个正整数如果它和除了它自身以外的所有正因子之和相等我们称它为「完美数」Perfect Number。给定一个整数n如果是完美数返回true否则返回false。Tag模拟、数论、数学难度简单数据范围1 num 10^8示例示例 1输入num 28 输出true 解释28 1 2 4 7 14 1, 2, 4, 7, 和 14 是 28 的所有正因子。示例 2输入num 6 输出true示例 3输入num 496 输出true示例 4输入num 8128 输出true示例 5输入num 2 输出false从示例可以看到判断的关键在于两点一是正确枚举出除自身以外的全部正因子二是对因子求和并与原数比较。前四个示例恰好就是最小的四个完美数 6、28、496、8128而 2 的因子只有 11 ≠ 2因此返回false。核心思路朴素枚举的缺陷与成对因子优化拿到题目最容易想到的做法是从1到num - 1逐个判断能否整除并累加但num上限是10^8线性枚举在最坏情况下需要执行约10^8次取模运算虽然勉强能过但显然不是最优解。原题解给出的关键洞察是正因子总是成对出现的。例如28的因子对为(1, 28)、(2, 14)、(4, 7)每一对中较小的因子一定不超过sqrt(num)。因此我们只需要枚举每对正因子中的较小数即从[1, sqrt(num)]范围内枚举即可num 1时成立枚举到一个小因子i后配对的大因子num / i可以直接算出并一并累加。这样一来枚举量从O(num)直接降到O(sqrt(num))对10^8规模的数据只需约10^4次迭代。数学解法边界、溢出与平方根特判原题解的参考代码如下Javaclass Solution { public boolean checkPerfectNumber(int num) { if (num 1) return false; int ans 1; for (int i 2; i num / i; i) { if (num % i 0) { ans i; if (i * i ! num) ans num / i; } } return ans num; } }这段代码非常精简背后有三个值得细讲的工程细节1. 为什么num 1直接返回false1除了自身以外没有任何正因子因子和空和为00 ≠ 1因此直接返回false。若不特判下面的循环i从2开始不会执行ans初始化为1ans num会错误地判定1为完美数所以这一行是必须的。2. 用i num / i代替i sqrt(num)的动机原题解明确说明使用i num / i作为上界判断目的是避免调用sqrt库函数以及整数溢出。如果写i Math.sqrt(num)需要引入浮点库函数浮点开方在精度与性能上都劣于纯整数比较如果写i * i num当num接近10^8时i最大约10^4i * i不会溢出但若题目数据范围进一步扩大i * i在int下可能溢出为负数从而破坏循环条件。而i num / i全程使用整数除法既无浮点误差也不会溢出是处理这类「以平方根为上界」问题的通用写法在仓库其他数学类题解中同样被反复采用参见 Index/数学.md 收录的 367. 有效的完全平方数、441. 排列硬币等题。3.i * i ! num的平方根特判当num是完全平方数时其平方根i是唯一不与另一个不同因子配对的因子。例如num 36因子对为(1, 36)、(2, 18)、(3, 12)、(4, 9)、(6, 6)其中6只应计数一次。因此当num % i 0时先累加i再判断i * i ! num若i不是平方根说明num / i是另一个不同的因子一并累加若是平方根则num / i与i相等跳过避免重复计数。这正是成对枚举中唯一的重复风险点代码用一行判断干净地化解了它。累加初值ans 1的含义由于循环从i 2开始因子1被跳过因此将ans的初值直接设为1等价于把1这一因子预先计入。这与题目「除了它自身以外的所有正因子之和」的定义严格对齐——1计入、num自身不计入因为成对枚举时大因子num / i的最小取值就是i 2时给出的num / 2永远不会取到num本身当num为素数时循环内一个因子都加不进去ans恰好等于1。复杂度分析时间复杂度O(sqrt(num))。循环上界为i num / i迭代次数不超过sqrt(num)量级对num 10^8上限仅需约10^4次迭代毫秒级完成。空间复杂度O(1)。仅使用常数个整型变量不依赖任何额外数据结构。在本题数据范围下该算法无论时间还是空间都是最优级别的表现ans的累加值在10^8内也不会超出int表示范围。边界用例验证与正确性论证输入因子除自身外因子和结果1无0false代码特判211false61, 2, 36true281, 2, 4, 7, 1428true361, 2, 3, 4, 6, 9, 12, 1855false验证平方根不重复计数4961, 2, 4, 8, 16, 31, 62, 124, 248496true8128全部真因子8128true其中36这个用例特别适合用来检验平方根特判若把6重复累加两次因子和会变成61 ≠ 36但按正确逻辑得到55 ≠ 36依然返回false因此特判的正确性在非完美完全平方数上体现得最清楚。数论背景延伸完美数家族与欧几里得-欧拉定理本题虽标记为「简单」背后却连接着一个经典的数论话题。完美数的研究可追溯到古希腊最早被确认的几个完美数正是题目示例中的6, 28, 496, 8128。数论中著名的欧几里得-欧拉定理给出结论偶完美数与梅森素数一一对应——若2^p - 1是素数则2^(p-1) * (2^p - 1)是偶完美数反之每个偶完美数都具有该形式。据此可以验证在本题1 num 10^8的范围内恰好存在 5 个完美数6, 28, 496, 8128, 33550336这也是另一种理论上可行的「打表」思路仓库中另有 Index/打表.md 专题可供参考。值得说明的是是否存在奇完美数至今是数论中未解决的问题目前已知的完美数均为偶数。这些背景能帮助你理解为什么题目给出的示例恰好是这些数字但在本题的约束下成对因子枚举的模拟解法才是通用、稳妥且可迁移的首选。仓库归类与延伸学习本题在原仓库中被同时归入「数学/数论」与「模拟」两个专题Index/数学.md收录 507. 完美数 的题解链接与 367. 有效的完全平方数、441. 排列硬币、633. 平方数之和等因子与平方根类题目归为一类Index/模拟.md从「按规则逐项统计」的视角将本题与 166. 分数到小数、400. 第 N 位数字 等模拟类简单题并列。如果你希望进一步巩固本解法中用到的技巧可以按以下顺序延伸阅读仓库内相关题解367. 有效的完全平方数数学/二分同样围绕sqrt与整数平方根判断体会i num / i这类整数写法的通用性441. 排列硬币数学/二分同样需要以平方根级别上界做枚举/二分的数学题633. 平方数之和数学/双指针继续练习因子与平方根视角的组合使用若想挑战同类但更复杂的「因子统计」问题可阅读 Index/数论相关题解 中难度更高的题目。小结LeetCode 507「完美数」是一道典型的用数学性质优化模拟的入门题。核心要点可总结为三条正因子成对出现只需枚举到sqrt(num)即可覆盖所有因子复杂度从O(num)降为O(sqrt(num))用i num / i作为循环上界避开sqrt库函数与整数乘法溢出两种隐患对完全平方数做i * i ! num特判避免平方根因子被重复累加并正确处理num 1的边界。掌握这套「成对因子枚举」的写法后你不仅能在本题轻松 AC还能将它直接迁移到其他因子统计、因子和计算的题目中。完整的原始题解与仓库全部系列文章可在 LeetCode/501-510/507. 完美数简单.md 及 README.md 中查看。赞分享教程文档【免费下载链接】LogicStack-LeetCode公众号「宫水三叶的刷题日记」刷穿 LeetCode 系列文章源码项目地址https://gitcode.com/gh_mirrors/lo/LogicStack-LeetCode点击查看免费下载相关推荐LogicStack-LeetCode 题解精读LeetCode 952 按公因数计算最大组件大小枚举质因数 并查集LogicStack LeetCode 题解精读LeetCode 952 按公因数计算最大组件大小枚举质因数 并查集 本文基于 LogicStack教程文档LogicStack-LeetCode 题解精讲LeetCode 1775 通过最少操作次数使数组的和相等枚举 贪心 数学LogicStack LeetCode 题解精讲LeetCode 1775 通过最少操作次数使数组的和相等枚举 贪心 数学 本篇技术指南围绕「宫水教程文档LogicStack-LeetCode 题解精讲整数转罗马数字的贪心模拟解法LeetCode 12 中等LogicStack LeetCode 题解精讲整数转罗马数字的贪心模拟解法LeetCode 12 中等 本文以「宫水三叶的刷题日记」刷穿 LeetCod教程文档上一篇Whispering动态分析在运行时检测安全漏洞的方法下一篇从分享页到直链LinkSwift 如何完成 8 大网盘直链解析的完整旅程创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考