LeetCode 每日一题刷到 1390 这道“四因数”时我以为又是一道纯粹的数学题结果做下来发现它把因数枚举、边界处理、性能优化全揉在了一起。题面很简单给你一个整数数组 nums对数组里每个元素 x如果 x 恰好有四个因数就把这四个因数的和累加到答案里最后返回总和。比如 nums [21, 4, 7]21 的因数是 1、3、7、21恰好 4 个和为 32而 4 的因数是 1、2、4 只有 3 个7 的因数是 1、7 只有 2 个都不符合条件所以答案是 32。这道题比较适合刚接触算法刷题、想巩固数论基础的人。它不需要什么高深技巧但能把“枚举因数”“质因数分解”“时间复杂度估算”这些基本功串起来是你从暴力解法走向高效解法的很好过渡。我自己在写题解和重构代码的过程中踩了几个挺隐蔽的坑所以这篇把完整思路、数学原理、代码实现、优化方案和调试过程都拆开讲讲。1. 题目解读与核心思路拆解1.1 题目到底在问什么先别急着写代码把题目要求拆清楚。输入是一个整数数组 nums输出是所有“恰好有四个因数”的元素其全部因数之和的累加结果。注意三个关键词恰好四个因数多一个少一个都不行。因数必须是正整数按照数学定义正因数包括 1 和它本身。累加的是“因数和”不是“因数的个数”也不是“符合条件的元素个数”。很多人第一反应是那我直接把每个数的所有因数找出来数一数是不是 4 个再把它们加起来不就行了听起来没毛病但问题很快会暴露怎么“把所有因数找出来”最朴素的做法从 1 到 x 逐个取模能整除的就是因数。这个思路在数字小的时候完全没问题可一旦 x 变大比如 x 99991你就要循环近十万次。如果 nums 数组有一万个元素最坏情况下要做十亿次取模运算超时几乎是必然的。所以这道题真正考的不是“会不会找因数”而是“能不能少找一些数就判定因数个数”。这就引出了因数成对出现的性质。1.2 因数成对出现找到一半等于找到全部对于任意正整数 x如果一个数 d 能整除 x那么 x / d 也一定能整除 x。也就是说因数总是成对出现的。比如 12 的因数有 1 和 12、2 和 6、3 和 4三对。这个性质的价值在于我们根本不需要从 1 遍历到 x只需要从 1 遍历到根号 x。遇到一个能整除的 d就把 d 和 x / d 同时记录下来。因为 d 超过根号 x 之后x / d 一定小于根号 x这些配对在之前就已经被发现了。唯一需要注意的是完全平方数。比如 16因数有 1 和 16、2 和 8、4 和 4。当 d 4 时x / d 也等于 4这时候不能把 4 记两次否则因数个数就多算了。这是后面代码里最容易出错的地方我一开始就漏了这个判断导致 16、25、36 这类平方数全部统计错误。1.3 为什么不能盲目暴力理论上枚举到根号 x 已经能解决大部分问题但面试或竞赛场景里还要看数据规模。假如 nums 长度为 10^4每个数最大是 10^5那么枚举到根号 x 的复杂度是 O(n * sqrt(max))约等于 10^4 * 316 316 万次操作这个量级在主流在线评测系统里完全能过。可如果每个数变成 10^9sqrt 之后变成 31623再乘上 10^4 就是 3 亿次那就很危险了。所以我在写题解时把“枚举到根号”作为第一版方案因为它最容易写对也最容易理解。但如果想进一步压榨性能或者应对更大的数据范围就得走向质因数分解这条路这个后面单独开一节细说。先掌握枚举法因为你至少要保证在常规约束下能写出一个不超时、不出边界错误的版本。2. 核心算法实现与复杂度分析2.1 枚举到 sqrt(x) 的通用解法我的第一版实现用的是最常见的枚举因数思路复杂度 O(n * sqrt(m))代码也很直白class Solution: def sumFourDivisors(self, nums: List[int]) - int: total 0 for x in nums: divisor_sum 0 divisor_count 0 d 1 while d * d x: if x % d 0: divisor_sum d divisor_count 1 if d ! x // d: divisor_sum x // d divisor_count 1 d 1 if divisor_count 4: total divisor_sum return total关键点在于 while 循环的边界条件d * d x。为什么不用d sqrt(x)因为浮点数开方会有精度问题万一遇到大数边界sqrt可能产生微小误差导致循环少一次或多一次。用乘法判定更稳纯整数运算不会出错。每次找到能整除的 d我先把 d 加进因数和计数加一然后判断 d 和 x // d 是否相等。不相等时才把另一个因数也加进去。这个判断是整道题最容易丢分的地方漏掉它完全平方数会变成“因数个数少一个”比如 16 会统计为 6 个因数而不是正确的 5 个。2.2 复杂度分析为什么 316 万次操作很稳很多初学者对“复杂度”没概念我来算一笔账。假设 nums 长度为 n数组中最大值不超过 M。上面的代码对每个 x循环次数是 sqrt(x) 次总循环次数是 sum(sqrt(nums[i]))上界是 n * sqrt(M)。按 LeetCode 原题常规约束假设 n 10^4M 10^5sqrt(M) ≈ 316总操作约 316 万次。即使每次循环里还有取模、加法、比较总共也就几千万条指令现代 CPU 跑完不到 0.1 秒实测提交时间在几十毫秒左右非常稳。空间复杂度是 O(1)只用了几个临时变量。2.3 为什么“恰好四个因数”只有两种形态其实这道题有个更快的判断方式知道这个数学结论代码可以更简洁。设 x 的标准分解式为x p1^a1 * p2^a2 * ... * pk^ak根据因数个数公式x 的因数个数为 (a1 1) * (a2 1) * ... * (ak 1)。要让因数个数恰好等于 4只有两种情况第一种x p^3也就是某个质数的立方。此时因数个数是 3 1 4四个因数分别是 1、p、p^2、p^3。第二种x p * q其中 p 和 q 是两个不同的质数。此时因数个数是 (1 1) * (1 1) 4四个因数分别是 1、p、q、pq。换句话说恰好有四个因数的数要么是某个质数的三次方要么是两个不同质数的乘积。这里有个很容易踩的陷阱p * p 不满足条件因为因数只有 1、p、p^2一共 3 个不是 4 个。所以平方数不等于四个因数。这个结论有什么用如果你不想枚举所有因数可以先对 x 做质因数分解然后根据质因数的个数和指数直接判断。如果分解结果是 1 个质数且指数为 3答案加 1 p p^2 p^3如果分解结果是 2 个不同质数且指数都是 1答案加 1 p q p*q其他情况一律跳过。3. 优化思路与质因数分解方案3.1 从因数个数公式到判定优化虽然枚举到根号已经能过题但我在写第二版时还是想试试质因数分解的方案主要目的是提升单个数很大时的鲁棒性。比如 nums[i] 能达到 10^9 或更大时枚举到根号就变成最多 31623 次循环如果数组长度也很大可能会超时。质因数分解的思路是对每个 x从 2 开始逐个试除统计每个质因数的指数。为了加速试除同样只需要试到根号 x。如果一个数在试除完后还大于 1说明它本身是一个大于根号的质因子。这里需要格外小心两点一是计数过程不能用集合或列表保存所有因数否则空间会变大二是必须区分“同一个质数出现多次”的情况比如 x 8 2^3质因数表是 {2: 3}符合第一种形态。再比如 x 12 2^2 * 3质因数表是 {2: 2, 3: 1}因数个数是 3 * 2 6不符合条件。3.2 质因数分解的实现细节下面是基于因数个数公式的优化版实现class Solution: def sumFourDivisors(self, nums: List[int]) - int: total 0 for x in nums: tmp x factors {} d 2 while d * d tmp: if tmp % d 0: cnt 0 while tmp % d 0: tmp // d cnt 1 factors[d] cnt d 1 if tmp 1: factors[tmp] factors.get(tmp, 0) 1 if len(factors) 1: p, e next(iter(factors.items())) if e 3: total 1 p p * p p * p * p elif len(factors) 2: vals list(factors.items()) if vals[0][1] 1 and vals[1][1] 1: p, q vals[0][0], vals[1][0] total 1 p q p * q return total这段代码的思路是先分解出所有质因子及指数再根据因数个数公式判断因子总数是否为 4。注意我在内层循环里用一个 cnt 记录同一个质数的出现次数这样后续判断指数是否为 3 或 1 就很方便。不过我实测之后发现在 LeetCode 原题的数据规模下这个优化版的代码反而不如第一版直观因为每次都要维护一个字典有哈希开销实际运行时间并不比枚举法快多少。它的优势主要在于当数据范围放大、枚举到根号已经吃力时能够显著降低单个数的时间消耗。如果你只是刷这道题用枚举法就行如果你想在更大的数据范围下做扩展质因数分解方案值得掌握。3.3 两种解法怎么选我在本地把两种写法都跑了一遍针对不同数据规模做了简单对拍结论是这样的方案时间复杂度单个数空间复杂度适合场景风险点枚举因数到 sqrt(x)O(sqrt(x))O(1)数据范围 10^5 以内代码最简单平方数去重容易漏质因数分解O(sqrt(x))但常数更大O(质因子个数)需要扩展到大数或需要念及因数个数公式字典维护复杂索引容易错从复杂度看两者最坏情况都是 O(sqrt(x))所以理论上差距不大。但实际运行时枚举法因为没有额外的哈希结构常数更小所以在 LeetCode 1390 的约束下反而更快。质因数分解的价值更多在于“数学通吃”因为因数个数公式本身能处理任何数量的因数判定而不只针对“恰好四个”这一种情况。如果你在面试中遇到这道题我建议先从枚举法讲起然后在面试官追问“能不能更快”时再引出质因数分解和因数个数公式。这样既展示了基础能力又体现了数学功底。4. 常见问题与调试实录4.1 特判 1 和 0 的处理一开始写代码时我没有考虑 x 1 的情况。1 的因数只有 1 一个显然不符合四因数条件。但如果用枚举法循环条件直接变成 1 * 1 1d 1能整除divisor_count 变成 1不是 4所以会自动跳过。x 0 在题目约束里一般不会出现因为正整数因数定义下 0 没有意义但如果你在本地测试时遇到最好明确跳过避免除零错误。我在调试时特意加了这样的边界测试assert sumFourDivisors([1]) 0 assert sumFourDivisors([2]) 0 assert sumFourDivisors([4]) 0 assert sumFourDivisors([8]) 0 assert sumFourDivisors([16]) 0 assert sumFourDivisors([21]) 32 assert sumFourDivisors([27]) 408 的因数是 1、2、4、8刚好 4 个和是 15等等这里要重新算一下8 2^3四个因数是 1、2、4、8和是 15。27 3^3四个因数是 1、3、9、27和是 40。这类质数的三次方是最容易遗漏的情况因为很多人只想到两个质数相乘忘了三次方形态。4.2 平方数到底坑在哪里这道题调试中最大的坑就是完全平方数。假设 x 16枚举因数时遇到 d 4x // d 4两个因子相等。如果代码没有加if d ! x // d的判断就会把 4 加两次导致因数个数变成 61、2、4、4、8、16和变成 35严重出错。更隐蔽的是 36因数有 1、2、3、4、6、9、12、18、36一共 9 个也不是四因数。但因为它存在 d 6 时 x // d 6 的情况如果去重逻辑没写好计数会错得更离谱。所以我在调试时养成了一个习惯构造一批平方数和非平方数混合的测试用例用枚举法跑一遍再用质因数分解法对拍结果。如果两种解法输出的答案一致基本可以认为去重逻辑没问题。4.3 实际提交中的性能观察第一次提交时我用的几乎是裸的暴力枚举从 1 循环到 x结果在 LeetCode 上一个比较极端的测试用例上运行时间超过了 1500ms直接被判定超时。改成枚举到 sqrt(x) 后提交时间降到了 80ms 左右。后来我用一个长度为 10000、元素都接近 100000 的数组做本地压测枚举到 sqrt(x) 的版本只用了约 90ms质因数分解版本约 120ms。这个差距不大但足以说明在这种量级下完全没必要上复杂的优化。如果你发现自己写的代码还是慢可以检查以下几点是不是没有用d * d x而是反复调用math.sqrt(x)后者会引入浮点运算开销虽然不大但没必要。是不是在循环内部使用了列表收集因数每收集一个都触发内存分配会拖慢速度。是不是把循环边界计算放在内层应该先算好再循环。4.4 常见问题速查表症状可能原因解决方案完全平方数计数错误没有处理 d x // d 的情况加 if 判断相等时只加一次超时循环到 x 而不是 sqrt(x)改为 while d * d x结果偏大重复统计因数检查去重逻辑质因数分解方案结果错误统计质因子指数时覆盖了同名 key用 cnt 变量保存指数再写入字典边界测试崩溃没有处理 x 1主动跳过或依赖计数条件自然跳过5. 从这道题延伸开去的数论套路写到这里想再说一个我刷题时总结的通用套路凡是让你判断“因数个数”“因数之和”的题目优先往因数成对、唯一分解定理、因数个数公式这三个方向想。比如“一个正整数是否恰好有 K 个因数”通用解法是分解质因数后相乘。如果 K 是 3那这个数必须是质数的平方如果 K 是 5必须是某个质数的四次方如果 K 是 6可能是 p^5 或 p^2 * q。这类问题一旦能用质因数角度思考题目的变化就不大了。LeetCode 1390 是一个很好的入门样例因为它的约束条件决定了枚举法也能过所以对新朋友很友好同时它又有足够深的数学背景方便进一步优化和扩展。代码写成什么样不是重点重点是你能否清晰地解释“为什么恰好四个因数只有两种形态”这比背模板重要得多。我自己在刷这道题时最有收获的一点是不要因为题目简单就跳过边界条件的推演完全平方数、1、质数的三次方这几个特判让我在之后做其他因数类题目时少踩了很多坑。如果你也打算坚持每日一题建议每道题做完后都问自己一句这个题的核心数学性质是什么边界条件在哪是否有比标准解法更本质的规律这样刷十道比盲目刷五十道有价值得多。
