千问 LeetCode 3098. 求出所有子序列的能量和 Rust实现

这是一道经典的算法题LeetCode 3098要求计算数组中所有长度为 k 的子序列的“能量”之和。子序列的能量定义为子序列中任意两个元素差值绝对值的最小值。核心思路1. 排序预处理由于子序列的能量只与元素的差值有关与元素的原始顺序无关我们可以先对数组进行升序排序。排序后子序列中任意两元素差值绝对值的最小值一定等于相邻元素差值的最小值。2. 记忆化搜索 (DFS Memoization)我们需要枚举所有长度为 k 的子序列并在枚举的过程中实时维护当前的最小差值。定义一个深度优先搜索函数其状态需要包含以下四个参数* i当前正在遍历的数组下标。* prev_idx上一个被选入子序列的元素下标用于计算当前元素与上一个元素的差值。* cnt当前子序列还需要选取的元素个数。* min_diff当前子序列已经确定的最小差值。3. 状态转移与边界* 当 cnt 0 时说明已经选够了 k 个元素返回当前的 min_diff。* 如果剩余的元素数量不足以凑齐 cnt 个直接返回 0 进行剪枝。* 对于当前元素 nums[i]我们有两种选择* 不选状态转移到 dfs(i 1, prev_idx, cnt, min_diff)。* 选如果这是子序列的第一个元素prev_idx 为特殊标记min_diff 保持不变否则更新 min_diff min(min_diff, nums[i] - nums[prev_idx])。状态转移到 dfs(i 1, i, cnt - 1, new_min_diff)。4. 记忆化缓存由于状态空间较大直接使用递归会导致超时。我们可以使用 HashMap 将这四个状态参数组合成一个唯一的键Key来进行记忆化缓存从而大幅降低时间复杂度。Rust 实现代码use std::collections::HashMap;impl Solution {pub fn sum_of_powers(nums: Veci32, k: i32) - i32 {let mut nums nums;nums.sort(); // 1. 排序保证相邻元素的差值即为最小差值let n nums.len();let mut memo: HashMap(usize, usize, i32, i32), i64 HashMap::new();const MOD: i64 1_000_000_007;// 2. 定义记忆化搜索函数fn dfs(i: usize,prev_idx: usize,cnt: i32,min_diff: i32,nums: Veci32,memo: mut HashMap(usize, usize, i32, i32), i64) - i64 {// 边界条件选够了 k 个元素if cnt 0 {return min_diff as i64;}// 剪枝剩余元素不够选if i nums.len() || nums.len() - i cnt as usize {return 0;}// 3. 检查记忆化缓存let state (i, prev_idx, cnt, min_diff);if let Some(res) memo.get(state) {return res;}const MOD: i64 1_000_000_007;let mut res 0;// 选择 1不选当前元素 nums[i]res (res dfs(i 1, prev_idx, cnt, min_diff, nums, memo)) % MOD;// 选择 2选当前元素 nums[i]let new_min_diff if prev_idx nums.len() {// 如果是子序列的第一个元素min_diff 保持初始值min_diff} else {// 否则更新最小差值min_diff.min(nums[i] - nums[prev_idx])};res (res dfs(i 1, i, cnt - 1, new_min_diff, nums, memo)) % MOD;// 存入缓存memo.insert(state, res);res}// 4. 启动 DFSprev_idx 初始化为 n (表示尚未选择任何元素)let result dfs(0, n, k, i32::MAX, nums, mut memo);(result % MOD) as i32}}代码细节说明* 状态键的设计Rust 的 HashMap 支持元组Tuple作为 Key因此我们直接使用 (i, prev_idx, cnt, min_diff) 作为状态标识这比字符串拼接或位运算更加直观且安全。* 特殊标记 prev_idx我们将 prev_idx 的初始值设为 nums.len()以此来判断当前选取的元素是否为子序列的第一个元素。如果是第一个元素则不需要计算差值min_diff 保持为 i32::MAX。* 数据类型由于结果可能非常大中间计算过程使用 i64 进行累加并在每次加法后对 10^9 7 取模最后再转换为 i32 返回。