2024-09-25：用 go 语言，给定一个长度为 n 的整数数组 nums 和一个正整数 k，定义数组的“能量“为所有和为 k 的子序列的数量之和。请计算 nums 数组中所有子序列的能量和，并对

作者：福大大架构师每日一题

2024-09-25
北京
本文字数：1104 字
阅读完需：约 4 分钟

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] 。

所以答案为 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 完整代码如下：

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 完整代码如下：

const MOD: i64 = 1_000_000_007;
fn sum_of_power(nums: Vec<i32>, k: i32) -> i64 {    let k = k as usize;    let mut f = vec![0; k + 1];    f[0] = 1;        for &x in nums.iter() {        for j in (0..=k).rev() {            if j >= x as usize {                f[j] = (f[j] * 2 + f[j - x as usize]) % MOD;            } else {                f[j] = f[j] * 2 % MOD;            }        }    }        f[k]}
fn main() {    let nums = vec![1, 2, 3];    let k = 3;    println!("{}", sum_of_power(nums, k));}