千问 LeetCode 2862. 完全子集的最大元素和 TypeScript实现

TypeScript 的实现其实就是给 JavaScript 版本加上严格的类型约束。逻辑完全一致，但 TS 的代码在规范性和可维护性上会更好。

TypeScript 代码实现

function maximumSum(nums: number[]): number {
let maxSum = 0;
const n = nums.length;
// 使用 Map 记录每个“无平方因子数”对应的元素和
const sumMap = new Map<number, number>();

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: number): number => {
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); // 记得向下取整
}
// 如果质因数个数是奇数，则保留一个 i 到结果中
if (count % 2 === 1) {
core *= i;
}
}
// 如果最后剩下的 n 大于 1，说明它是一个大质因数，且个数为 1（奇数）
if (n > 1) {
core *= n;
}
return core;
};

另一种更巧妙的解法（枚举法）

除了提取核心数，这道题还有一种非常巧妙的枚举思路。

根据数学规律，任意一个“完全子集”的下标都可以表示为 {x, 4x, 9x, 16x...}（即 k² * x）。我们可以直接枚举这个基数 x（x 从 1 遍历到 n），然后不断累加 x * 1², x * 2², x * 3²... 对应的数组元素，直到下标超出数组长度为止。

这种方法不需要做质因数分解，代码会更加简洁：

function maximumSum(nums: number[]): number {
let maxSum = 0;
const n = nums.length;

// 枚举基数 x (从 1 到 n)
for (let x = 1; x <= n; x++) {
let currentSum = 0;
// 枚举平方数倍数 k²，计算下标 x * k²
for (let k = 1; k * k * x <= n; k++) {
// 下标是 x * k * k，对应的数组索引需要减 1
currentSum += nums[x * k * k - 1];
}
// 实时更新最大值
maxSum = Math.max(maxSum, currentSum);
}

return maxSum;
};

复杂度与选择
* 提取核心数法：时间复杂度 O(N * √N)，空间复杂度 O(N)（需要 Map 存储分组和）。
* 枚举基数法：时间复杂度同样是 O(N * √N)（调和级数推导），但空间复杂度是 O(1)，且代码极其简短。

在面试或实际刷题中，如果你能快速推导出枚举法的规律，直接写第二种会非常加分！