调试中...
困难
相关标签
相关企业
提示
给你一个长度为 n 的整数数组 nums 和一个 正 整数 k 。
一个 的 能量 定义为子序列中 任意 两个元素的差值绝对值的 最小值 。
请你返回 nums 中长度 等于 k 的 所有 子序列的 能量和 。
由于答案可能会很大，将答案对 109 + 7 取余 后返回。
示例 1：
输入：nums = [1,2,3,4], k = 3
输出：4
解释：
nums 中总共有 4 个长度为 3 的子序列：[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 的子序列是 [2,2] 。能量和为 |2 - 2| = 0 。
示例 3：
输入：nums = [4,3,-1], k = 2
输出：10
解释：
nums 总共有 3 个长度为 2 的子序列：[4,3] ，[4,-1] 和 [3,-1] 。能量和为 |4 - 3| + |4 - (-1)| + |3 - (-1)| = 10 。
提示：
2 <= n == nums.length <= 50-108 <= nums[i] <= 1082 <= k <= n
通过次数
10.7K
提交次数
19.7K
通过率
54.5%
相关企业
提示 1
Sort
nums.提示 2
There are at most
n2 distinct differences.提示 3
For a particular difference
d, let dp[len][i][j] be the number of subsequences of length len in the subarray nums[0..i] where the last element picked was at index j.提示 4
For each index, we can check if it can be picked if
nums[i] - nums[j] <= d.相似题目
评论 (0)
贡献者
© 2025 领扣网络（上海）有限公司
0 人在线