LeetCode 1390. 四因数
目录
题目描述
题意分析
给定一个整数数组
nums，对其中恰好有四个正因数的每个整数，把它的四个因数加起来；最后返回所有这些和的总和。如果数组里没有任何一个数满足条件，返回 0。要抓住的第一个字眼是「恰好」。因数个数多于 4 或少于 4 的数都不计入，所以判断必须是精确的相等，不能是「至少四个」。
第二个字眼是「四个因数之和」，包括 1 和它自身。比如 21 的因数是 1、3、7、21，和为 32。不是「真因数之和」，也不是「除自身外的因数之和」。
第三个要点是求和对象：题目要的是所有合格数字的因数和再加总，而不是合格数字本身的和，也不是合格数字的个数。
约束里
nums.length最多 $10^4$，每个元素最大 $10^5$。两个规模合起来是关键信号：如果对每个数从 1 枚举到它本身，代价是 $10^4 \times 10^5 = 10^9$，会超时；而枚举到平方根只需 $10^4 \times \sqrt{10^5} \approx 3.2 \times 10^6$，轻松通过。这组约束在明示「因数枚举必须只走到平方根」。边界要留意四点：1 只有一个因数（就是 1 自己），不合格；完全平方数在平方根处只贡献一个因数而不是两个；数组里可能一个合格数都没有，此时返回 0；同一个数字可能在数组里出现多次，每次都要独立计入。
解法：枚举因子
核心思路
因数成对出现：若
d整除x，另一个因数就是x / d。每对因数中至少一个不超过 $\sqrt{x}$，因此只枚举满足d * d <= x的d，即可找到全部因数。维护
count和sum。发现一对不同因数时，数量加 2、和加d + x/d；若d == x/d，说明x是完全平方数，平方根只能计一次。循环包含等号正是为了处理这个平方边界。不变量是：处理完当前
d后，count与sum分别等于目前发现的不同因数个数及其总和。每个非平方根因数只属于唯一的一对，平方根又被单独计一次，所以最终统计不重不漏。因数个数只会增加，一旦
count > 4，该数不可能再满足“恰好四个”，可立即返回 0。不能在count == 4时提前成功，因为后面可能继续发现因数；例如 24 在处理因数 1、2 后已有四个已发现因数，但实际共有八个。对每个数组元素返回“恰有四个因数时的因数和，否则为 0”，再累加即可。
解题步骤
- 遍历
nums，为当前数将count、sum初始化为 0。- 从
d = 1枚举到d * d <= x；不整除时跳过。- 令配对因数
other = x / d。二者相等时只计一个，否则同时计入两个。- 若
count > 4，当前数立即返回 0；枚举结束后仅在count == 4时返回sum。- 把每个合格数的因数和加入总答案。
样例
21找到(1,21)、(3,7)，得到四个因数和 32。对于平方数4，第二次找到的是(2,2)，只能增加一个因数，所以总数是 3。反例24在发现(1,24)、(2,12)后仍不能提前判定成功，继续枚举会发现更多因数。
代码实现
class Solution {
public int sumFourDivisors(int[] nums) {
int total = 0;
for (int x : nums) {
total += divisorSumIfFour(x);
}
return total;
}
private int divisorSumIfFour(int x) {
int count = 0;
int sum = 0;
for (int d = 1; d * d <= x; d++) {
if (x % d != 0) {
continue;
}
int other = x / d;
count++;
sum += d;
if (other != d) {
count++;
sum += other;
}
if (count > 4) {
return 0;
}
}
return count == 4 ? sum : 0;
}
}
func sumFourDivisors(nums []int) int {
total := 0
for _, x := range nums {
total += divisorSumIfFour(x)
}
return total
}
func divisorSumIfFour(x int) int {
count, sum := 0, 0
for d := 1; d*d <= x; d++ {
if x%d != 0 {
continue
}
other := x / d
count++
sum += d
if other != d {
count++
sum += other
}
if count > 4 {
return 0
}
}
if count == 4 {
return sum
}
return 0
}
复杂度分析
- 时间复杂度：$O(n\sqrt C)$，其中 $n$ 是数组长度、$C$ 是数组最大值；更精确地说是 $O(\sum_i\sqrt{nums_i})$。
- 空间复杂度：$O(1)$，只维护常数个计数与求和变量。
关键点总结
- 因数按
(d, x/d)成对发现，只需枚举到平方根。d * d <= x中的等号不能漏；平方根与自身配对时只能计一次。- “恰好四个”只能在完整枚举后确认，超过四个则可立即失败。
- 每个数组元素独立统计，局部
count、sum不能跨元素复用。- 本题范围下平方根枚举足够，不需要额外筛法或质因数分解结构。
易错点总结
- 循环写成
d * d < x会漏掉平方根。x = 16时因数 4 不会被发现。- 平方根按两个因数计。
x = 4会被错误统计为四个因数并贡献 9，而实际只有 1、2、4。- 在
count == 4时提前返回成功。x = 24会先发现四个因数，随后其实还有更多。- 只累加较小因数
d，会漏掉配对的x/d；21应贡献1+3+7+21=32。- 把合格数字本身或合格数字数量加入答案，都会误解题目要求的“因数之和”。
- 对每个数不重置统计变量，会让相邻数组元素互相污染。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 1492. n 的第 k 个因子 | 中等 | 同为因数枚举，但要按升序定位第 k 个，成对收集后需要注意配对顺序 |
| 507. 完美数 | 简单 | 求真因数和并与自身比较，枚举范围同样到平方根，但要排除自身 |
| 204. 计数质数 | 中等 | 批量判质数要用埃氏筛或线性筛，与本题「单个数试除」形成时间空间的取舍对照 |
| 728. 自除数 | 简单 | 判定条件换成「每一位都能整除自身」，考的是数位拆解而非因数分解 |
| 172. 阶乘后的零 | 中等 | 把问题化归为统计因子 5 的个数，是质因数视角的经典应用 |
| 263. 丑数 | 简单 | 反复除以 2、3、5 判断剩余，训练质因数分解的循环写法 |
| 264. 丑数 II | 中等 | 由生成而非判定得到第 n 个丑数，需要三指针合并有序序列 |
| 367. 有效的完全平方数 | 简单 | 用二分或牛顿迭代避开浮点开方，正好呼应本题 d * d <= x 的写法 |
| 69. x 的平方根 | 简单 | 整数开方的标准解法，是理解「枚举到平方根」这一边界的基础 |
| 633. 平方数之和 | 中等 | 双指针在平方值域上收缩，同样把枚举范围压到 $\sqrt{c}$ |
| 279. 完全平方数 | 中等 | 转为完全背包求最少个数，说明平方数结构也能用 DP 处理 |
| 50. Pow(x, n) | 中等 | 快速幂把 $O(n)$ 压到 $O(\log n)$，与本题一样靠数学性质砍复杂度 |
| 1071. 字符串的最大公因子 | 简单 | 把字符串周期问题化归为长度的最大公约数，训练发现隐藏数论结构的能力 |
| 786. 第 K 个最小的质数分数 | 中等 | 在质数集合上做二分或堆，属于因数枚举之外的另一类数论题 |