DeepSeek LeetCode 2681.英雄的力量 Java实现

以下是 LeetCode 2681“英雄的力量”的 Java 实现。解题思路1. 理解题意所有非空子集中最大值² × 最小值的和2. 优化暴力直接枚举子集2^n会超时需要 O(n log n) 或 O(n) 解法3. 排序 前缀和· 排序后每个元素作为最小值时其右侧元素作为最大值· 对每个 i计算以 nums[i] 为最小值的所有子集的力量和· 利用前缀和快速计算数学推导设排序后数组为 a[0] ≤ a[1] ≤ ... ≤ a[n-1]对于以 a[i] 为最小值a[j] 为最大值的子集· 中间元素i1 到 j-1可以任意选或不选· 共有 2^(j-i-1) 个子集· 贡献为 a[i] * a[j]² * 2^(j-i-1)总答案 Σ_{i0}^{n-1} Σ_{ji}^{n-1} a[i] * a[j]² * 2^(j-i-1)当 ij 时2^(-1)1/2需要特殊处理更优雅的推导力扣官方解法答案 Σ_{i0}^{n-1} a[i] * (Σ_{ji}^{n-1} a[j]² * 2^{j-i-1})其中当 ji 时2^{-1} 视为 1空集情况只有一个元素的子集Java 代码javaclass Solution {private static final int MOD 1_000_000_007;public int sumOfPower(int[] nums) {Arrays.sort(nums);int n nums.length;long[] pow2 new long[n];pow2[0] 1;for (int i 1; i n; i) {pow2[i] (pow2[i - 1] * 2) % MOD;}long ans 0;long prefixSum 0; // 前缀和Σ a[j] * 2^{j}for (int i 0; i n; i) {// 当前元素作为最大值的情况long maxPower (long) nums[i] * nums[i] % MOD;// 情况1子集只有当前元素ans (ans maxPower * nums[i]) % MOD;// 情况2当前元素作为最大值前面元素作为最小值ans (ans maxPower * prefixSum) % MOD;// 更新前缀和当前元素作为未来更大值的最小值候选prefixSum (prefixSum * 2 nums[i]) % MOD;}return (int) ans;}}优化版本更清晰的实现javaclass Solution {private static final int MOD 1_000_000_007;public int sumOfPower(int[] nums) {Arrays.sort(nums);int n nums.length;long ans 0;long prefixSum 0; // 前缀和Σ a[j] * 2^{j}for (int i 0; i n; i) {long val nums[i];// 以当前元素为最大值的贡献long contribution (val * val) % MOD;contribution contribution * ((prefixSum val) % MOD) % MOD;ans (ans contribution) % MOD;// 更新前缀和当前元素会成为后续元素的最小值候选prefixSum (prefixSum * 2 val) % MOD;}return (int) ans;}}详细推导版本javaclass Solution {private static final int MOD 1_000_000_007;public int sumOfPower(int[] nums) {Arrays.sort(nums);int n nums.length;// 预计算 2 的幂long[] pow2 new long[n 1];pow2[0] 1;for (int i 1; i n; i) {pow2[i] (pow2[i - 1] * 2) % MOD;}long ans 0;for (int i 0; i n; i) {// nums[i] 作为最小值long minVal nums[i];// 枚举最大值位置 jfor (int j i; j n; j) {long maxVal nums[j];long power (maxVal * maxVal) % MOD;long count;if (i j) {count 1; // 只有一个元素的子集} else {count pow2[j - i - 1]; // 中间元素任意选}long contribution minVal * power % MOD;contribution contribution * count % MOD;ans (ans contribution) % MOD;}}return (int) ans;}}算法示例java// 示例nums [2,1,4]// 排序后[1,2,4]// 遍历过程// i0 (val1):// prefixSum0// contribution 1² * (0 1) 1// ans 1// prefixSum 0*2 1 1//// i1 (val2):// contribution 2² * (1 2) 4 * 3 12// ans 1 12 13// prefixSum 1*2 2 4//// i2 (val4):// contribution 4² * (4 4) 16 * 8 128// ans 13 128 141//// 结果141复杂度分析· 时间复杂度O(n log n)排序的复杂度· 空间复杂度O(1) 或 O(n)如果预计算 2 的幂关键点说明1. 排序的重要性排序后可以明确最小值和最大值的关系2. 前缀和的妙用prefixSum 维护了 Σ a[j] * 2^{j} 避免重复计算3. 模运算所有乘法都要取模防止溢出4. 公式推导· 对于每个最大值 a[i]它对答案的贡献是 a[i]² * (所有可能的子集最小值之和)· 所有可能的子集最小值之和 a[0]*2⁰ a[1]*2¹ ... a[i]*2ⁱ这个解法利用了排序和数学优化将 O(2^n) 的暴力枚举优化到 O(n log n)。