2025-07-31：最多 K 个元素的子序列的最值之和。用go语言，给定一个整数数组 nums 和一个正整数 k，求所有非空子序列中，长度不超过 k 的那些子序列的“最大元素和最小元素之和”的累加和。需要注意的是，子序列是从原数组中删去部分元素（顺序不变）得到的序列。
由于结果可能非常庞大，请将最终答案对 1000000007 取模后返回。
1 <= nums.length <= 100000。
0 <= nums[i] <= 1000000000。
1 <= k <= min(100, nums.length)。
输入： nums = [5,0,6], k = 1。
输出： 22。
解释：
对于长度恰好为 1 的子序列，最小值和最大值均为元素本身。因此，总和为 5 + 5 + 0 + 0 + 6 + 6 = 22。
题目来自力扣3428。
示例分析
以 nums = [5, 0, 6] 和 k = 1 为例：
- 长度为 1 的子序列有
[5],[0],[6]，每个子序列的最大和最小都是元素本身，因此总和为(5 + 5) + (0 + 0) + (6 + 6) = 22。
解题思路
- 排序数组：首先将数组
nums排序。这样我们可以方便地计算每个元素作为最小值和最大值的情况。 - 组合数学：对于排序后的数组，计算每个元素
nums[i]作为子序列的最小值和最大值时的贡献。- 对于
nums[i]作为最小值：它出现在子序列中时，子序列的其他元素必须大于或等于nums[i]（即来自nums[i..n-1]）。 - 对于
nums[i]作为最大值：它出现在子序列中时，子序列的其他元素必须小于或等于nums[i]（即来自nums[0..i]）。
- 对于
- 动态计算系数：对于每个
nums[i]，我们需要计算它在多少个子序列中作为最小值和最大值。这可以通过组合数来计算：- 作为最小值：子序列必须包含
nums[i]，且其他元素从nums[i+1..n-1]中选，子序列长度不超过k。 - 作为最大值：子序列必须包含
nums[i]，且其他元素从nums[0..i-1]中选，子序列长度不超过k。
- 作为最小值：子序列必须包含
- 快速计算组合数：为了高效计算组合数，预先计算阶乘和逆阶乘数组（模
1000000007），这样可以在 O(1) 时间内计算组合数C(n, m)。 - 对称性利用：排序后，
nums[i]作为最小值的贡献与nums[n-1-i]作为最大值的贡献是对称的。因此可以同时计算两者的贡献。
具体步骤
- 排序数组：将
nums排序，得到sorted_nums。 - 初始化阶乘和逆阶乘数组：
- 预计算
f[i] = i! mod 1000000007。 - 预计算
invF[i] = (i!)^-1 mod 1000000007（利用费马小定理）。
- 预计算
- 动态计算系数：
- 初始化一个系数
s，表示当前nums[i]和nums[n-1-i]的贡献系数。 - 对于每个
i，更新s为s * 2 - C(i, k-1)（模1000000007），这是因为：- 每次迭代，
s表示前i个元素和对称的后i个元素的贡献系数。 s * 2表示扩展子序列长度时的贡献。- C(i, k-1)是减去超过长度k的子序列的贡献。
- 每次迭代，
- 初始化一个系数
- 累加贡献：
- 对于每个
i，将sorted_nums[i] + sorted_nums[n-1-i]乘以系数s累加到结果中。
- 对于每个
- 返回结果：最终结果对
1000000007取模。
时间和空间复杂度
- 时间复杂度：
- 排序：
O(n log n)。 - 预计算阶乘和逆阶乘：
O(n)。 - 动态计算系数和累加贡献：
O(n)。 - 总时间复杂度：
O(n log n)（排序主导）。
- 排序：
- 空间复杂度：
- 阶乘和逆阶乘数组：
O(n)。 - 排序：
O(log n)（快速排序的递归栈）。 - 总空间复杂度：
O(n)。
- 阶乘和逆阶乘数组：
Go完整代码如下：
package mainimport ("fmt""slices"
)const mod = 1_000_000_007
const mx = 100_000var f [mx]int // f[i] = i!
var invF [mx]int // invF[i] = i!^-1func init() {f[0] = 1for i := 1; i < mx; i++ {f[i] = f[i-1] * i % mod}invF[mx-1] = pow(f[mx-1], mod-2)for i := mx - 1; i > 0; i-- {invF[i-1] = invF[i] * i % mod}
}func pow(x, n int) int {res := 1for ; n > 0; n /= 2 {if n%2 > 0 {res = res * x % mod}x = x * x % mod}return res
}func comb(n, m int) int {if m > n {return 0}return f[n] * invF[m] % mod * invF[n-m] % mod
}func minMaxSums(nums []int, k int) (ans int) {slices.Sort(nums)s := 1for i, x := range nums {ans = (ans + s*(x+nums[len(nums)-1-i])) % mods = (s*2 - comb(i, k-1) + mod) % mod}return
}func main() {nums := []int{5, 0, 6}k := 1result := minMaxSums(nums, k)fmt.Println(result)
}
Python完整代码如下：
# -*-coding:utf-8-*-MOD = 10**9 + 7
MX = 100_000# 预处理阶乘和逆元
f = [1] * MX
invF = [1] * MXdef pow_mod(x, n):res = 1while n > 0:if n & 1:res = res * x % MODx = x * x % MODn >>= 1return resdef init():for i in range(1, MX):f[i] = f[i-1] * i % MODinvF[MX-1] = pow_mod(f[MX-1], MOD-2)for i in range(MX-1, 0, -1):invF[i-1] = invF[i] * i % MODdef comb(n, m):if m > n or m < 0:return 0return f[n] * invF[m] % MOD * invF[n-m] % MODdef minMaxSums(nums, k):nums.sort()n = len(nums)ans = 0s = 1for i, x in enumerate(nums):ans = (ans + s * (x + nums[n - 1 - i])) % MODs = (s * 2 - comb(i, k-1) + MOD) % MODreturn ansif __name__ == "__main__":init()nums = [5, 0, 6]k = 1print(minMaxSums(nums, k))
