Hard

题目描述

给你一个长度为 n 的整数数组 nums 和一个正整数 k。

子序列的 能力值 定义为子序列中任意两个元素之间的最小绝对差值。

返回 nums 中所有长度等于 k 的子序列的能力值之和。

由于答案可能很大，请返回答案对 10^9 + 7 取模的结果。

示例 1：

输入：nums = [1,2,3,4], k = 3
输出：4
解释：
nums 中长度为 3 的子序列有 4 个：[1,2,3]、[1,3,4]、[1,2,4] 和 [2,3,4]。
能力值之和为 |2 - 3| + |3 - 4| + |2 - 1| + |3 - 4| = 4。

示例 2：

输入：nums = [2,2], k = 2
输出：0
解释：
nums 中长度为 2 的子序列只有 1 个：[2,2]。
能力值之和为 |2 - 2| = 0。

示例 3：

输入：nums = [4,3,-1], k = 2
输出：10
解释：
nums 中长度为 2 的子序列有 3 个：[4,3]、[4,-1] 和 [3,-1]。
能力值之和为 |4 - 3| + |4 - (-1)| + |3 - (-1)| = 10。

提示：

  • 2 <= n == nums.length <= 50
  • -10^8 <= nums[i] <= 10^8
  • 2 <= k <= n

解题思路

这道题要求计算所有长度为 k 的子序列的能力值之和，其中能力值定义为子序列中任意两个元素的最小绝对差值。

核心思路是使用动态规划：

  1. 排序预处理：首先对数组排序，这样相邻元素的差值就是可能的最小差值候选。

  2. 枚举所有可能的差值：由于数组长度最多 50，所有可能的差值最多有 n² 个。我们可以枚举每个差值 d，计算有多少个子序列的最小差值恰好等于 d。

  3. 动态规划状态设计：

    • dp[len][i][j] 表示在 nums[0..i] 范围内，选择长度为 len 的子序列，且最后一个元素在位置 j 的方案数
    • 对于固定的差值 d，我们只考虑那些相邻元素差值 >= d 的子序列

  4. 状态转移：

    • 对于每个位置 i，我们可以选择将其加入子序列
    • 如果 nums[i] - nums[j] >= d，则可以从状态 dp[len-1][j-1][j] 转移到 dp[len][i][i]

  5. 计算贡献：对于每个差值 d，统计最小差值恰好为 d 的子序列数量，然后乘以 d 加入答案。

时间复杂度主要来自枚举所有差值和动态规划的状态转移。

代码实现

class Solution {
public:
    int sumOfPowers(vector<int>& nums, int k) {
        const int MOD = 1e9 + 7;
        int n = nums.size();
        sort(nums.begin(), nums.end());
        
        set<int> diffSet;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                diffSet.insert(nums[j] - nums[i]);
            }
        }
        
        vector<int> diffs(diffSet.begin(), diffSet.end());
        long long result = 0;
        
        for (int d : diffs) {
            vector<vector<vector<long long>>> dp(k + 1, 
                vector<vector<long long>>(n, vector<long long>(n, 0)));
            
            // 初始化长度为1的子序列
            for (int i = 0; i < n; i++) {
                dp[1][i][i] = 1;
            }
            
            // 动态规划
            for (int len = 2; len <= k; len++) {
                for (int i = 0; i < n; i++) {
                    for (int j = 0; j < i; j++) {
                        if (nums[i] - nums[j] >= d) {
                            for (int prev = 0; prev <= j; prev++) {
                                dp[len][i][j] = (dp[len][i][j] + dp[len-1][j][prev]) % MOD;
                            }
                        }
                    }
                }
            }
            
            // 统计最小差值为d的子序列数量
            long long count = 0;
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < i; j++) {
                    if (nums[i] - nums[j] == d) {
                        count = (count + dp[k][i][j]) % MOD;
                    }
                }
            }
            
            result = (result + (1LL * d * count) % MOD) % MOD;
        }
        
        return result;
    }
};

class Solution:
    def sumOfPowers(self, nums: List[int], k: int) -> int:
        MOD = 10**9 + 7
        n = len(nums)
        nums.sort()
        
        # 获取所有可能的差值
        diffs = set()
        for i in range(n):
            for j in range(i + 1, n):
                diffs.add(nums[j] - nums[i])
        
        result = 0
        
        for d in diffs:
            # dp[len][i][j] = 长度为len，范围在[0,i]，最后元素在j的子序列数
            dp = [[[0] * n for _ in range(n)] for _ in range(k + 1)]
            
            # 初始化长度为1的情况
            for i in range(n):
                dp[1][i][i] = 1
            
            # 动态规划
            for length in range(2, k + 1):
                for i in range(n):
                    for j in range(i):
                        if nums[i] - nums[j] >= d:
                            for prev in range(j + 1):
                                dp[length][i][j] = (dp[length][i][j] + dp[length-1][j][prev]) % MOD
            
            # 统计最小差值恰好为d的子序列数
            count = 0
            for i in range(n):
                for j in range(i):
                    if nums[i] - nums[j] == d:
                        count = (count + dp[k][i][j]) % MOD
            
            result = (result + d * count) % MOD
        
        return result

public class Solution {
    public int SumOfPowers(int[] nums, int k) {
        const int MOD = 1000000007;
        int n = nums.Length;
        Array.Sort(nums);
        
        HashSet<int> diffSet = new HashSet<int>();
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                diffSet.Add(nums[j] - nums[i]);
            }
        }
        
        List<int> diffs = new List<int>(diffSet);
        long result = 0;
        
        foreach (int d in diffs) {
            long[,,] dp = new long[k + 1, n, n];
            
            // 初始化长度为1的子序列
            for (int i = 0; i < n; i++) {
                dp[1, i, i] = 1;
            }
            
            // 动态规划
            for (int len = 2; len <= k; len++) {
                for (int i = 0; i < n; i++) {
                    for (int j = 0; j < i; j++) {
                        if (nums[i] - nums[j] >= d) {
                            for (int prev = 0; prev <= j; prev++) {
                                dp[len, i, j] = (dp[len, i, j] + dp[len - 1, j, prev]) % MOD;
                            }
                        }
                    }
                }
            }
            
            // 统计最小差值为d的子序列数量
            long count = 0;
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < i; j++) {
                    if (nums[i] - nums[j] == d) {
                        count = (count + dp[k, i, j]) % MOD;
                    }
                }
            }
            
            result = (result + ((long)d * count) % MOD) % MOD;
        }
        
        return (int)result;
    }
}

var sumOfPowers = function(nums, k) {
    const MOD = 1e9 + 7;
    const n = nums.length;
    nums.sort((a, b) => a - b);
    
    const memo = new Map();
    
    function dp(pos, count, lastIdx, minDiff) {
        if (count === k) {
            return minDiff;
        }
        if (pos === n || n - pos < k - count) {
            return 0;
        }
        
        const key = `${pos},${count},${lastIdx},${minDiff}`;
        if (memo.has(key)) {
            return memo.get(key);
        }
        
        let result = 0;
        
        // Skip current element
        result = (result + dp(pos + 1, count, lastIdx, minDiff)) % MOD;
        
        // Take current element
        let newMinDiff = minDiff;
        if (count > 0) {
            newMinDiff = Math.min(minDiff, nums[pos] - nums[lastIdx]);
        }
        result = (result + dp(pos + 1, count + 1, pos, newMinDiff)) % MOD;
        
        memo.set(key, result);
        return result;
    }
    
    return dp(0, 0, -1, Infinity);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值
时间复杂度O(n^5 × k)
空间复杂度O(k × n^2)

其中 n 是数组长度，k 是子序列长度。时间复杂度来自枚举 O(n^2) 个差值，每个差值需要 O(k × n^3) 的动态规划计算。空间复杂度主要来自三维 DP 数组的存储。

相关题目