Hard

题目描述

给你一个下标从 1 开始的数组 nums。你的任务是从 nums 中选择一个完整子集，使得每对选中的下标相乘都是完全平方数。也就是说，如果你选择了 ai 和 aj，那么 i * j 必须是完全平方数。

返回具有最大和的完整子集的和。

示例 1：

输入: nums = [8,7,3,5,7,2,4,9]
输出: 16
解释: 
我们选择下标 2 和 8 处的元素，2 * 8 = 16 是完全平方数。

示例 2：

输入: nums = [8,10,3,8,1,13,7,9,4]
输出: 20
解释:
我们选择下标 1、4、9 处的元素。1 * 4、1 * 9、4 * 9 都是完全平方数。

约束条件：

  • 1 <= n == nums.length <= 10^4
  • 1 <= nums[i] <= 10^9

提示：

  • 定义 P(x) 为 x 的质因数分解中指数为奇数的质数的乘积。例如：对于 x = 18，分解为 2^1 × 3^2，P(18) = 2；对于 x = 45，分解为 3^2 × 5^1，P(45) = 5；对于 x = 50，分解为 2^1 × 5^2，P(50) = 2；对于 x = 210，分解为 2^1 × 3^1 × 5^1 × 7^1，P(210) = 210。
  • 如果 P(i) = P(j)，那么 nums[i] 和 nums[j] 可以组合在一起。
  • 选择和最大的组。

解题思路

思路分析

这道题的关键在于理解什么时候两个下标的乘积是完全平方数。

首先，我们需要理解完全平方数的性质：一个数是完全平方数当且仅当它的质因数分解中所有质数的指数都是偶数。

对于两个数 i 和 j，如果 i * j 是完全平方数，那么 i * j 的质因数分解中所有质数的指数都必须是偶数。这意味着对于任何质数 p，如果 p 在 i 的分解中指数为奇数，那么 p 在 j 的分解中指数也必须为奇数，这样相乘后指数才会是偶数。

根据题目提示，我们定义函数 P(x) 为 x 的质因数分解中指数为奇数的质数的乘积。两个数 i 和 j 能够组合在一起（即 i * j 是完全平方数）当且仅当 P(i) = P(j)。

解题思路：

  1. 计算每个下标的 P 值
  2. 将具有相同 P 值的下标对应的数组元素分为一组
  3. 计算每组的元素和，返回最大值

为了高效计算 P(x)，我们只需要将 x 除以所有完全平方因子，剩下的就是 P(x)。

代码实现

class Solution {
public:
    long long maximumSum(vector<int>& nums) {
        int n = nums.size();
        unordered_map<int, long long> groups;
        
        for (int i = 1; i <= n; i++) {
            int p = getP(i);
            groups[p] += nums[i - 1];
        }
        
        long long result = 0;
        for (auto& [key, sum] : groups) {
            result = max(result, sum);
        }
        
        return result;
    }
    
private:
    int getP(int x) {
        int result = 1;
        for (int i = 2; i * i <= x; i++) {
            int count = 0;
            while (x % i == 0) {
                x /= i;
                count++;
            }
            if (count % 2 == 1) {
                result *= i;
            }
        }
        if (x > 1) {
            result *= x;
        }
        return result;
    }
};

class Solution:
    def maximumSum(self, nums: List[int]) -> int:
        n = len(nums)
        groups = defaultdict(int)
        
        def get_p(x):
            result = 1
            i = 2
            while i * i <= x:
                count = 0
                while x % i == 0:
                    x //= i
                    count += 1
                if count % 2 == 1:
                    result *= i
                i += 1
            if x > 1:
                result *= x
            return result
        
        for i in range(1, n + 1):
            p = get_p(i)
            groups[p] += nums[i - 1]
        
        return max(groups.values())

public class Solution {
    public long MaximumSum(IList<int> nums) {
        int n = nums.Count;
        Dictionary<int, long> groups = new Dictionary<int, long>();
        
        for (int i = 1; i <= n; i++) {
            int p = GetP(i);
            if (!groups.ContainsKey(p)) {
                groups[p] = 0;
            }
            groups[p] += nums[i - 1];
        }
        
        long result = 0;
        foreach (var sum in groups.Values) {
            result = Math.Max(result, sum);
        }
        
        return result;
    }
    
    private int GetP(int x) {
        int result = 1;
        for (int i = 2; i * i <= x; i++) {
            int count = 0;
            while (x % i == 0) {
                x /= i;
                count++;
            }
            if (count % 2 == 1) {
                result *= i;
            }
        }
        if (x > 1) {
            result *= x;
        }
        return result;
    }
}

var maximumSum = function(nums) {
    const n = nums.length;
    const groups = new Map();
    
    function getSquareFreeFactors(num) {
        let result = 1;
        let i = 2;
        while (i * i <= num) {
            let count = 0;
            while (num % i === 0) {
                num /= i;
                count++;
            }
            if (count % 2 === 1) {
                result *= i;
            }
            i++;
        }
        if (num > 1) {
            result *= num;
        }
        return result;
    }
    
    for (let i = 1; i <= n; i++) {
        const key = getSquareFreeFactors(i);
        if (!groups.has(key)) {
            groups.set(key, 0);
        }
        groups.set(key, groups.get(key) + nums[i - 1]);
    }
    
    return Math.max(...groups.values());
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n√n)对于每个下标 i，计算 P(i) 需要 O(√i) 时间，总共 n 个下标
空间复杂度O(n)最坏情况下每个下标都有不同的 P 值，需要存储 n 个分组

相关题目