2024-11-13：求出所有子序列的能量和。用 go 语言，给定一个整数数组 nums 和一个正整数 k，
定义一个子序列的能量为子序列中任意两个元素之间的差值绝对值的最小值。
找出 nums 中长度为 k 的所有子序列的能量和，
对结果取模 10^9 + 7 后返回。
输入：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 。
答案 2024-11-13：
chatgpt
题目来自 leetcode3098。
大体步骤如下：
1.输入解析：
2.预处理：
对 nums 进行排序，以便更容易处理差值。
计算所有可能的差值 vals，即对于每一对 (nums[i], nums[j])（i > j），计算 nums[i] - nums[j]，并将这些差值存入 vals。
将一个无穷大值 inf 添加到 vals 中，确保后续处理边界情况。
对 vals 进行排序并去重，得到唯一的差值数组。
3.动态规划数组初始化：
初始化三维数组 d，其中 d[i][p][v] 表示考虑到第 i 个元素，长度为 p 的子序列中，最小差值为 vals[v] 的子序列个数。
初始化二维数组 border，其中 border[i][p] 表示考虑到第 i 个元素，长度为 p 的子序列中，当前处理到的 vals 数组的索引边界。
初始化二维数组 sum 和 suf，用于计算前缀和和后缀和，以便快速更新 d 数组。
4.动态规划填充：
遍历 nums 中的每个元素 nums[i]，并对于每个 j < i，计算 nums[i] - nums[j] 在 vals 中的位置 pos。
对于每个可能的子序列长度 p（从 1 到 k），更新 d, sum, suf, 和 border 数组。
这一步的核心是利用前缀和和后缀和快速更新 d 数组，以及利用 border 数组来避免重复计算。
5.结果计算：
6.输出：
时间复杂度：
排序 nums：O(n log n)
生成 vals 并排序去重：O(n^2 log n^2)（因为最多有 n(n-1)/2 个差值，但去重和排序的复杂度较高）
动态规划填充：O(n^2 k m)，其中 n 是 nums 的长度，k 是子序列长度，m 是 vals 的长度（去重后的差值个数）。
结果计算：O(n m)
总时间复杂度：由于 m 最多为 n^2，因此总时间复杂度为 O(n^4 k)，但在实际情况下，由于 vals 的去重，m 通常远小于 n^2。
空间复杂度：
三维数组 d：O(n k m)
二维数组 border, sum, suf：O(n k) 和 O(k m)
其他辅助数组和变量：O(n^2)（用于存储差值 vals）
总空间复杂度：O(n k m + n^2)，同样地，由于 m 通常远小于 n^2，实际空间使用会更少。
综上所述，尽管理论上的时间复杂度和空间复杂度较高，但由于 vals 的去重和排序效率，以及动态规划过程中的前缀和、后缀和优化，实际运行时的性能可能会更好。
Go 完整代码如下：
package main
import ( "fmt" "sort")
const mod = 1e9 + 7const inf = 0x3f3f3f3f
func sumOfPowers(nums []int, k int) int { n := len(nums) sort.Ints(nums)
var vals []int for i := 0; i < n; i++ { for j := 0; j < i; j++ { vals = append(vals, nums[i]-nums[j]) } } vals = append(vals, inf) sort.Ints(vals) vals = unique(vals)
d := make([][][]int, n) for i := range d { d[i] = make([][]int, k+1) for j := range d[i] { d[i][j] = make([]int, len(vals)) } }
border := make([][]int, n) for i := range border { border[i] = make([]int, k+1) }
sum := make([][]int, k+1) for i := range sum { sum[i] = make([]int, len(vals)) }
suf := make([][]int, n) for i := range suf { suf[i] = make([]int, k+1) } for i := 0; i < n; i++ { for j := 0; j < i; j++ { pos := sort.SearchInts(vals, nums[i]-nums[j]) for p := 1; p <= k; p++ { for border[j][p] < pos { sum[p][border[j][p]] = (sum[p][border[j][p]] - suf[j][p] + mod) % mod sum[p][border[j][p]] = (sum[p][border[j][p]] + d[j][p][border[j][p]]) % mod suf[j][p] = (suf[j][p] - d[j][p][border[j][p]] + mod) % mod border[j][p]++ sum[p][border[j][p]] = (sum[p][border[j][p]] + suf[j][p]) % mod } } }
d[i][1][len(vals)-1] = 1 for p := 2; p <= k; p++ { for v := 0; v < len(vals); v++ { d[i][p][v] = sum[p-1][v] } } for p := 1; p <= k; p++ { for v := 0; v < len(vals); v++ { suf[i][p] = (suf[i][p] + d[i][p][v]) % mod } sum[p][0] = (sum[p][0] + suf[i][p]) % mod } }
res := 0 for i := 0; i < n; i++ { for v := 0; v < len(vals); v++ { res = (res + int(int64(vals[v])*int64(d[i][k][v])%mod)) % mod } } return res}
func unique(arr []int) []int { if len(arr) == 0 { return arr } result := []int{arr[0]} for _, v := range arr { if v != result[len(result)-1] { result = append(result, v) } } return result}
func main() { nums := []int{1, 2, 3, 4} k := 3 fmt.Println(sumOfPowers(nums, k))}
复制代码
Rust 完整代码如下：
use std::collections::HashSet;
const MOD: i32 = 1_000_000_007;const INF: i32 = 0x3f3f3f3f;
fn sum_of_powers(nums: Vec<i32>, k: usize) -> i32 { let n = nums.len(); let mut nums = nums; nums.sort();
let mut vals = Vec::new(); for i in 0..n { for j in 0..i { vals.push(nums[i] - nums[j]); } } vals.push(INF); vals.sort(); vals = unique(vals);
let mut d = vec![vec![vec![0; vals.len()]; k + 1]; n];
let mut border = vec![vec![0; k + 1]; n]; let mut sum = vec![vec![0; vals.len()]; k + 1]; let mut suf = vec![vec![0; k + 1]; n];
for i in 0..n { for j in 0..i { let pos = match vals.binary_search(&(nums[i] - nums[j])) { Ok(p) => p, Err(p) => p, }; for p in 1..=k { while border[j][p] < pos { sum[p][border[j][p]] = (sum[p][border[j][p]] - suf[j][p] + MOD) % MOD; sum[p][border[j][p]] = (sum[p][border[j][p]] + d[j][p][border[j][p]]) % MOD; suf[j][p] = (suf[j][p] - d[j][p][border[j][p]] + MOD) % MOD; border[j][p] += 1; sum[p][border[j][p]] = (sum[p][border[j][p]] + suf[j][p]) % MOD; } } }
d[i][1][vals.len() - 1] = 1; for p in 2..=k { for v in 0..vals.len() { d[i][p][v] = sum[p - 1][v]; } } for p in 1..=k { for v in 0..vals.len() { suf[i][p] = (suf[i][p] + d[i][p][v]) % MOD; } sum[p][0] = (sum[p][0] + suf[i][p]) % MOD; } }
let mut res = 0; for i in 0..n { for v in 0..vals.len() { res = (res + vals[v] as i64 * d[i][k][v] as i64 % MOD as i64) % MOD as i64; } } res as i32}
fn unique(mut arr: Vec<i32>) -> Vec<i32> { if arr.is_empty() { return arr; } arr.sort(); let mut result = Vec::new(); let mut prev = arr[0]; result.push(prev); for &v in &arr[1..] { if v != prev { result.push(v); prev = v; } } result}
fn main() { let nums = vec![1, 2, 3, 4]; let k = 3; println!("{}", sum_of_powers(nums, k));}
复制代码
评论