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：
题目来自leetcode3098。
大体步骤如下：
1.输入解析：
-
输入一个整数数组
nums和一个正整数k。 -
例如：
nums = [1, 2, 3, 4]，k = 3。
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.结果计算：
-
遍历每个
d[i][k][v]，其中i是nums的索引，k是子序列长度，v是vals的索引。 -
计算每个
d[i][k][v]对结果的贡献，即vals[v] * d[i][k][v]，并累加到res中。 -
对
res取模10^9 + 7后返回。
6.输出：
- 输出最终计算得到的
res。
时间复杂度：
-
排序
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 + 7
const 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));
}
