2024-09-25：用go语言，给定一个长度为 n 的整数数组 nums 和一

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.定义一个数组用于记录不同和值下的子序列数量，数组长度为，初始时令表示和为 0 时只有空子序列存在。

f

k+1

f[0] = 1

2.遍历给定的整数数组中的每个元素，对于每个，从开始向前遍历到 0，更新的值：

nums

k

f[j]

• •如果当前值，则更新。这表示新的和为的子序列数量是原来和为的子序列数量的两倍加上和为的子序列数量。
• j >= x
• f[j] = (f[j]*2 + f[j-x]) % mod
• j
• j
• j-x
• •如果当前值，则更新。这表示由于当前的无法和当前的相加得到新的和值，因此只能将和为的子序列数量乘以 2。
• j < x
• f[j] = f[j] * 2 % mod
• j
• j

3.最终返回，即所有和为的子序列的数量之和。

f[k]

k

总体的时间复杂度是 O(n * k)，其中 n 是的长度，k 是给定的正整数。

nums

空间复杂度为 O(k)。

Go完整代码如下：

packagemain
import(
"fmt"
)
funcsumOfPower(nums[]int,kint)int{
constmod=1_000_000_007
f:=make([]int,k+1)
f[0]=1
for_,x:=rangenums{
forj:=k;j>=0;j--{
ifj>=x{
f[j]=(f[j]*2+f[j-x])%mod
}else{
f[j]=f[j]*2%mod
}
}
}
returnf[k]
}
funcmain(){
nums:=[]int{1,2,3}
k:=3
fmt.Println(sumOfPower(nums,k))
}

Rust完整代码如下：

constMOD:i64=1_000_000_007;
fnsum_of_power(nums:Vec,k:i32)->i64{
letk=kasusize;
letmutf=vec![0;k+1];
f[0]=1;
for&xinnums.iter(){
forjin(0..=k).rev(){
ifj>=xasusize{
f[j]=(f[j]*2+f[j-xasusize])%MOD;
}else{
f[j]=f[j]*2%MOD;
}
}
}
f[k]
}
fnmain(){
letnums=vec![1,2,3];
letk=3;
println!("{}",sum_of_power(nums,k));
}