JavaScript 版本的实现思路和 Java 是完全一样的,不过 JS 写起来会稍微灵活一些。

我们可以利用 JavaScript 的 Map 来代替数组记录分组和,同时利用 Math.sqrt 来快速提取下标的“无平方因子数”(也就是核心数)。

核心思路回顾
1. 数学规律:任意一个“完全子集”的下标,都可以写成 {x, 4x, 9x, 16x...} 的形式(即 k² * x)。其中 x 就是该下标的“无平方因子数”。
2. 提取核心数:对每个下标进行质因数分解,把所有成对的质因数(平方因子)消掉,剩下的就是它的核心数 x。
3. 分组求和:核心数 x 相同的下标可以分在同一组,累加它们对应的数组元素值,最终的最大累加和就是答案。

JavaScript 代码实现

/**
 * @param {number[]} nums
 * @return {number}
 */
var maximumSum = function(nums) {
    let maxSum = 0;
    const n = nums.length;
    // 使用 Map 来记录每个“无平方因子数”对应的元素和
    const sumMap = new Map();
    
    for (let i = 0; i < n; i++) {
        // 获取当前下标 (i + 1) 对应的无平方因子数
        const core = getCore(i + 1);
        
        // 将当前元素值累加到对应的组中
        const currentSum = (sumMap.get(core) || 0) + nums[i];
        sumMap.set(core, currentSum);
        
        // 实时更新最大值
        maxSum = Math.max(maxSum, currentSum);
    }
    
    return maxSum;
};

// 计算数字 n 的“无平方因子数”
const getCore = (n) => {
    let core = 1;
    // 质因数分解
    for (let i = 2; i * i <= n; i++) {
        let count = 0;
        // 统计质因数 i 的个数
        while (n % i === 0) {
            count++;
            n = Math.floor(n / i); // JS除法可能产生小数,记得取整
        }
        // 如果质因数个数是奇数,则保留一个 i 到结果中
        if (count % 2 === 1) {
            core *= i;
        }
    }
    // 如果最后剩下的 n 大于 1,说明它是一个大质因数,且个数为 1(奇数)
    if (n > 1) {
        core *= n;
    }
    return core;
};

细节注意
1. 取整操作:JavaScript 在做除法时(如 n / i)可能会产生浮点数,所以在 while 循环中更新 n 时,一定要用 Math.floor() 向下取整,否则会导致死循环或计算错误。
2. Map 的使用:这里使用 Map 来存储分组和,相比数组更加节省空间,且不需要提前知道最大的核心数是多少。
3. 时间复杂度:依然是 O(N * √N),对于这道题的数据规模来说,JavaScript 的运行速度是完全足够的。1

 

更多推荐