LeetCode 题解工作台
求出所有子序列的能量和
给你一个长度为 n 的整数数组 nums 和一个 正 整数 k 。 一个 子序列 的 能量 定义为子序列中 任意 两个元素的差值绝对值的 最小值 。 请你返回 nums 中长度 等于 k 的 所有 子序列的 能量和 。 由于答案可能会很大，将答案对 10 9 + 7 取余 后返回。 示例 1： 输入…
3
题型
5
代码语言
3
相关题
当前训练重点
困难 · 状态·转移·动态规划
答案摘要
由于题目涉及子序列元素的最小差值，我们不妨对数组 进行排序，这样可以方便我们计算子序列元素的最小差值。 接下来，我们设计一个函数 $dfs(i, j, k, mi)$，表示当前处理到第 个元素，上一个选取的是第 个元素，还需要选取 个元素，当前的最小差值为 时，能量和的值。那么答案就是 $dfs(0, n, k, +\infty)$。（若上一个选取的是第 个元素，表示之前没有选取过元素…
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 状态·转移·动态规划 题型思路
题目描述
给你一个长度为 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
解题思路
方法一：记忆化搜索
由于题目涉及子序列元素的最小差值，我们不妨对数组 进行排序，这样可以方便我们计算子序列元素的最小差值。
接下来，我们设计一个函数 ，表示当前处理到第 个元素，上一个选取的是第 个元素，还需要选取 个元素，当前的最小差值为 时，能量和的值。那么答案就是 。（若上一个选取的是第 个元素，表示之前没有选取过元素）
函数 的执行过程如下：
- 如果 ，表示已经处理完了所有的元素，如果 ，返回 ，否则返回 ；
- 如果剩余的元素个数 不足 个，返回 ；
- 否则，我们可以选择不选取第 个元素，可以获得的能量和为 ；
- 也可以选择选取第 个元素。如果 ，表示之前没有选取过元素，那么可以获得的能量和为 ；否则，可以获得的能量和为 。
- 我们累加上述结果，并对 取模后返回。
为了避免重复计算，我们可以使用记忆化搜索的方法，将已经计算过的结果保存起来。
时间复杂度 ，空间复杂度 。其中 为数组的长度。
class Solution:
def sumOfPowers(self, nums: List[int], k: int) -> int:
@cache
def dfs(i: int, j: int, k: int, mi: int) -> int:
if i >= n:
return mi if k == 0 else 0
if n - i < k:
return 0
ans = dfs(i + 1, j, k, mi)
if j == n:
ans += dfs(i + 1, i, k - 1, mi)
else:
ans += dfs(i + 1, i, k - 1, min(mi, nums[i] - nums[j]))
ans %= mod
return ans
mod = 10**9 + 7
n = len(nums)
nums.sort()
return dfs(0, n, k, inf)
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity depends on iterating through n elements for each subsequence length up to k, with potential nested loops for difference calculations. Space complexity depends on maintaining a DP table of size n by k. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Sorting the array hints at simplifying subsequence power calculation.
- question_mark
Using a DP table suggests a state transition approach for subsequences of length k.
- question_mark
Watch for overlapping subsequences to avoid redundant computations.
常见陷阱
外企场景- error
Not sorting nums, which complicates minimum absolute difference calculation.
- error
Incorrect DP state transition, leading to missed subsequences or wrong sums.
- error
Failing to aggregate only subsequences of exact length k.
进阶变体
外企场景- arrow_right_alt
Compute maximum instead of minimum absolute difference for subsequences of length k.
- arrow_right_alt
Return sum of powers for all subsequences up to length k instead of exactly k.
- arrow_right_alt
Handle subsequences with additional constraints, such as even sum or bounded elements.