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

这道题是一道非常经典的数学思维题。解决它的核心在于发现“完全子集”下标的数学规律。核心思路解析题目要求选出的子集中任意两个元素的下标乘积 i * j 都必须是一个完全平方数。通过数学推导唯一分解定理我们可以得出一个极其重要的结论任意一个“完全子集”的下标一定可以表示为 {x, 4x, 9x, 16x, ...} 的形式即 {1*x, 2²*x, 3²*x, 4²*x, ...}。为什么我们可以把任意一个下标 i 拆解为 i k² * x其中 x 是一个“无平方因子数”即 x 的质因数分解中所有质因数的指数都是1。当且仅当两个下标 i 和 j 拆解后得到的 x 相等时它们的乘积 i * j 才会是一个完全平方数。因此解题步骤如下1. 遍历数组的所有下标1 到 n。2. 对每个下标进行质因数分解提取出它对应的“无平方因子数” x也就是把所有成对的质因数消掉剩下的部分。3. 将所有对应同一个 x 的下标所指向的数组元素值累加。4. 最终的最大累加和就是我们要的答案。Java 代码实现class Solution {public long maximumSum(ListInteger nums) {long maxSum 0;int n nums.size();// 使用数组来记录每个“无平方因子数”对应的元素和// 大小为 n 1因为下标是从 1 开始的long[] sum new long[n 1];for (int i 0; i n; i) {// 获取当前下标 (i 1) 对应的无平方因子数int core getCore(i 1);// 将当前元素值累加到对应的组中sum[core] nums.get(i);// 实时更新最大值maxSum Math.max(maxSum, sum[core]);}return maxSum;}// 计算数字 n 的“无平方因子数”即提取出奇数次幂的质因数乘积private int getCore(int n) {int core 1;// 质因数分解for (int i 2; i * i n; i) {int count 0;// 统计质因数 i 的个数while (n % i 0) {count;n / i;}// 如果质因数个数是奇数则保留一个 i 到结果中if (count % 2 1) {core * i;}}// 如果最后剩下的 n 大于 1说明它是一个大于 sqrt(原n) 的质因数且个数为 1奇数if (n 1) {core * n;}return core;}}复杂度分析* 时间复杂度O(N * √N)。我们需要遍历 N 个元素对每个下标进行质因数分解的时间复杂度是 O(√N)。* 空间复杂度O(N)。需要一个长度为 N1 的数组来存储各个分组的累加和。