🍀 初学者友好指南 'Four Divisors' – LeetCode 1390 (C++, Python, JavaScript)

Source: Dev.to

问题概述

给定：

• 一个名为 nums 的整数数组。

目标：

• 找出数组中恰好有四个约数的所有数字。
• 对这些数字的所有约数求和，并返回总和。

思路

约数是能够整除另一个数且余数为 0 的数。例如，6 的约数是 1、2、3、6。

本解法使用 预计算：我们一次性计算出所有可能的数（最大到 100 000）的约数个数和约数和，然后对每个元素的查询在 O(1) 时间内完成。

筛法思路

• 外层循环 (i) – 遍历可能的约数。
• 内层循环 (j) – 遍历 i 的所有倍数。因为 i 能整除 j，我们就把 j 的约数计数加一，并把 i 加到 j 的约数和中。

构建完这些表后，检查一个数是否恰好有四个约数以及获取它的约数和，只需要一次数组查找。

代码块

C++

#include 
using namespace std;

constexpr int MX = 100001;
int divisor_num[MX];
int divisor_sum[MX];

// Precompute divisor counts and sums for all numbers up to 100,000
int init = [] {
    for (int i = 1; i & nums) {
        int ans = 0;
        for (int x : nums) {
            if (x  int:
        total_ans = 0
        for x in nums:
            if divisor_num[x] == 4:
                total_ans += divisor_sum[x]
        return total_ans

JavaScript

const MX = 100001;
const divisor_num = new Int32Array(MX);
const divisor_sum = new Int32Array(MX);

// Precompute using a self‑invoking function
(function() {
    for (let i = 1; i < MX; i++) {
        for (let j = i; j < MX; j += i) {
            divisor_num[j]++;
            divisor_sum[j] += i;
        }
    }
})();

/**
 * @param {number[]} nums
 * @return {number}
 */
var sumFourDivisors = function(nums) {
    let totalAns = 0;
    for (let x of nums) {
        if (divisor_num[x] === 4) {
            totalAns += divisor_sum[x];
        }
    }
    return totalAns;
};

关键要点

• 预计算： 当多个查询在固定范围内进行时，事先计算结果可以显著降低运行时间。
• 筛法模式： 将“逐个检查每个数”转变为“标记每个倍数”，可将复杂度从 O(N·√N) 降至大约 O(N log N)。
• 空间‑时间权衡： 使用额外的内存（约 10 万大小的数组）可以在处理输入数组时获得巨大的速度提升。

最后思考

本题展示了数论技术（如基于筛的预计算）在软件工程中的实际应用。类似的思路也是密码算法（例如 RSA）的基础，并且在搜索引擎或缓存系统等需要快速响应查询而对适度内存使用有容忍度的领域中非常有用。