LeetCode 1390. 四因数

约 5 分钟
文章信息 6 个分类 2 个标签
分类
LeetCode CodeTop 中等 未解决 1-2 字节
标签
数组 数学

题目描述

✅ 1390. 四因数

image-20260929082532534

image-20260929082532628

题意分析

对数组中的每个正整数，判断它是否恰好有四个不同的正因数。如果满足条件，就把这四个因数的和计入总答案；否则该整数贡献零。

正因数包括一和这个数自身，求的是因数之和，不是满足条件的整数之和。数组中相同整数若出现多次，也应按每次出现分别贡献。

解法：枚举因子

核心思路

[!blue]

因数总是成对出现：如果 d 能整除 x，另一因数就是 x / d。一对因数中至少有一个不超过平方根，所以只枚举满足 d * d <= x 的候选，就能覆盖全部因数，不必从一检查到 x。

发现一对因数时，先计入 d，若另一因数与它不同，再计入 x / d。两者相同只会发生在完全平方数的平方根处，这时必须只计一次，否则会把同一个因数重复统计。

对当前整数维护已发现因数个数 count 和它们的和 sum。若个数超过四，可以立即返回零，因为继续枚举只会增加因数，不可能重新变回四个。

反过来，刚发现四个时还不能认定成功，后面可能继续找到其他因数。只有扫描完平方根范围、确认恰好四个时，才能贡献当前因数和。每个数组元素都独立执行这项检查，最后累加贡献。

解题步骤

  1. 对当前整数初始化因数个数和因数和为零。
  2. 从一枚举到平方根，不整除就跳过。
  3. 整除时加入当前因数及配对因数，平方根重合时只加一次。
  4. 个数超过四就立即贡献零；完整枚举后恰好四个才贡献因数和。
  5. 汇总所有数组元素的贡献并返回。

代码实现

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(\sum_i\sqrt{nums_i})$，每个整数最多枚举到其平方根，超过四因数时可以提前停止。
  • 辅助空间复杂度：$O(1)$，只保存当前整数的计数、因数和以及总答案。

关键点总结

[!green]

  • 成对枚举把检查范围缩小到平方根，同时覆盖一和自身。
  • 平方根对应同一个因数，只计一次。
  • 超过四个可立即失败，恰好四个必须等枚举完成才能确认。

易错点总结

[!yellow]

  • 找到四个就提前成功，会遗漏后面出现的第五个或更多因数。
  • 平方根重复计数会把实际因数数量较少的平方数误判为合格。
  • 只累加 d 而漏掉配对值 x / d，会同时算错数量和总和。
  • 每个整数要重置局部统计，不能把前一个数的因数数量沿用下来。
  • 合格时累加的是全部因数的和，不是当前整数本身。

相似题目

题目 难度 关联与区别
507. 完美数 简单 同样成对枚举因子并累计和，本题还要求因子总数恰为4。
补充题 153. 整数的质因数分解 简单 四因数结构只可能是素数立方或两个不同素数之积，可由质因数重数理解。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2022/71219341
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！