Hard

题目描述

给你一个下标从 0 开始的整数数组 nums，表示一些英雄的力量值。一组英雄的 力量 定义如下：

  • 设 i0, i1, ... ,ik 为一组英雄的下标，那么这组英雄的力量为 max(nums[i0], nums[i1], ... ,nums[ik])² × min(nums[i0], nums[i1], ... ,nums[ik])。

返回所有可能的 非空 英雄组合的力量之和。由于答案可能非常大，请返回它对 10⁹ + 7 取模的结果。

示例 1：

输入：nums = [2,1,4]
输出：141
解释：
第1组：[2] 力量值 = 2² × 2 = 8
第2组：[1] 力量值 = 1² × 1 = 1
第3组：[4] 力量值 = 4² × 4 = 64
第4组：[2,1] 力量值 = 2² × 1 = 4
第5组：[2,4] 力量值 = 4² × 2 = 32
第6组：[1,4] 力量值 = 4² × 1 = 16
第7组：[2,1,4] 力量值 = 4² × 1 = 16
所有组合的力量之和 = 8 + 1 + 64 + 4 + 32 + 16 + 16 = 141

示例 2：

输入：nums = [1,1,1]
输出：7
解释：总共有7种可能的组合，每组的力量值都是1。因此所有组合的力量之和为7。

约束条件：

  • 1 <= nums.length <= 10⁵
  • 1 <= nums[i] <= 10⁹

解题思路

解题思路

这是一个数学和动态规划相结合的问题。关键观察是：对于排序后的数组，如果我们固定最大值和最小值，那么中间可以选择任意的元素子集。

核心分析：

  1. 首先对数组排序，这样便于确定最大值和最小值
  2. 对于排序后的数组，考虑以位置 j 的元素作为最大值的所有子数组
  3. 对于固定的最大值 nums[j]，最小值可以是 nums[0], nums[1], ..., nums[j] 中的任意一个
  4. 如果最小值是 nums[i] (i ≤ j)，那么中间的 j-i-1 个元素可以任意选择，共有 2^(j-i-1) 种组合

数学推导： 当我们固定最大值为 nums[j] 时，贡献的总和可以表示为： nums[j]² × Σ(nums[i] × 2^(j-i-1)) 其中 i 从 0 到 j

通过动态规划的思想，我们可以维护一个前缀和来高效计算这个表达式。设 dp 表示前面所有可能的最小值贡献，每次转移时：

  • 新的贡献 = 当前元素值 × 1 + 前面的贡献 × 2

这样可以在 O(n) 时间内完成计算。

代码实现

class Solution {
public:
    int sumOfPower(vector<int>& nums) {
        const int MOD = 1e9 + 7;
        sort(nums.begin(), nums.end());
        
        long long result = 0;
        long long dp = 0; // 前缀和：所有可能的最小值贡献
        
        for (long long num : nums) {
            // 当前数作为最大值时的总贡献
            result = (result + (num * num % MOD) * (num + dp) % MOD) % MOD;
            // 更新dp：当前数的贡献 + 之前贡献的两倍
            dp = (num + dp * 2) % MOD;
        }
        
        return result;
    }
};

class Solution:
    def sumOfPower(self, nums: List[int]) -> int:
        MOD = 10**9 + 7
        nums.sort()
        
        result = 0
        dp = 0  # 前缀和：所有可能的最小值贡献
        
        for num in nums:
            # 当前数作为最大值时的总贡献
            result = (result + pow(num, 2, MOD) * (num + dp)) % MOD
            # 更新dp：当前数的贡献 + 之前贡献的两倍
            dp = (num + dp * 2) % MOD
        
        return result

public class Solution {
    public int SumOfPower(int[] nums) {
        const int MOD = 1000000007;
        Array.Sort(nums);
        
        long result = 0;
        long dp = 0; // 前缀和：所有可能的最小值贡献
        
        foreach (long num in nums) {
            // 当前数作为最大值时的总贡献
            result = (result + (num * num % MOD) * (num + dp) % MOD) % MOD;
            // 更新dp：当前数的贡献 + 之前贡献的两倍
            dp = (num + dp * 2) % MOD;
        }
        
        return (int)result;
    }
}

var sumOfPower = function(nums) {
    const MOD = 1e9 + 7;
    nums.sort((a, b) => a - b);
    
    let result = 0;
    let dp = 0; // 前缀和：所有可能的最小值贡献
    
    for (let num of nums) {
        // 当前数作为最大值时的总贡献
        result = (result + (BigInt(num) * BigInt(num) % BigInt(MOD)) * BigInt(num + dp) % BigInt(MOD)) % BigInt(MOD);
        // 更新dp：当前数的贡献 + 之前贡献的两倍
        dp = (num + dp * 2) % MOD;
    }
    
    return Number(result);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

项目复杂度
时间复杂度O(n log n)
空间复杂度O(1)

说明：

  • 时间复杂度：O(n log n) 主要来自排序操作，遍历数组是 O(n)
  • 空间复杂度：O(1) 只使用了常数级别的额外空间