2024-09-25：用go语言，给定一个长度为 n 的整数数组 nums 和一个正整数 k，
定义数组的"能量"为所有和为 k 的子序列的数量之和。
请计算 nums 数组中所有子序列的能量和，并对结果取模 10^9 7 后返回。
输入：nums = [1,2,3], k = 3。
输出：6。
解释：
总共有 5 个能量不为 0 的子序列：
子序列 [1,2,3] 有 2 个和为 3 的子序列：[1,2,3] 和 [1,2,3] 。
子序列 [1,2,3] 有 1 个和为 3 的子序列：[1,2,3] 。
子序列 [1,2,3] 有 1 个和为 3 的子序列：[1,2,3] 。
子序列 [1,2,3] 有 1 个和为 3 的子序列：[1,2,3] 。
子序列 [1,2,3] 有 1 个和为 3 的子序列：[1,2,3] 。
所以答案为 2 1 1 1 1 = 6 。
答案2024-09-25：
chatgpt
题目来自leetcode3082。
大体步骤如下：
1.定义一个数组 f 用于记录不同和值下的子序列数量，数组长度为 k 1，初始时令 f[0] = 1 表示和为 0 时只有空子序列存在。
2.遍历给定的整数数组 nums 中的每个元素 x，对于每个 x，从 k 开始向前遍历到 0，更新 f[j] 的值：
- • 如果当前值
j >= x，则更新f[j] = (f[j]*2 f[j-x]) % mod。这表示新的和为j的子序列数量是原来和为j的子序列数量的两倍加上和为j-x的子序列数量。 - • 如果当前值
j < x，则更新f[j] = f[j] * 2 % mod。这表示由于当前的j无法和当前的x相加得到新的和值，因此只能将和为j的子序列数量乘以 2。
3.最终返回 f[k]，即所有和为 k 的子序列的数量之和。
总体的时间复杂度是 O(n * k)，其中 n 是 nums 的长度，k 是给定的正整数。
空间复杂度为 O(k)。
Go完整代码如下：
代码语言：javascript复制package main
import(
"fmt"
)
func sumOfPower(nums []int, k int)int{
const mod =1_000_000_007
f :=make([]int, k 1)
f[0]=1
for _, x :=range nums {
for j := k; j >=0; j--{
if j >= x {
f[j]=(f[j]*2 f[j-x])% mod
}else{
f[j]= f[j]*2% mod
}
}
}
return f[k]
}
func main(){
nums:=[]int{1,2,3}
k:=3
fmt.Println(sumOfPower(nums,k))
}
Rust完整代码如下：
代码语言：javascript复制const MOD:i64=1_000_000_007;
fnsum_of_power(nums:Vec<i32>, k:i32)->i64{
letk= k asusize;
letmut f=vec![0; k 1];
f[0]=1;
for&x in nums.iter(){
forjin(0..=k).rev(){
if j >= x asusize{
f[j]=(f[j]*2 f[j - x asusize])% MOD;
}else{
f[j]= f[j]*2% MOD;
}
}
}
f[k]
}
fnmain(){
letnums=vec![1,2,3];
letk=3;
println!("{}",sum_of_power(nums, k));
}
