2025-07-31：最多 K 个元素的子序列的最值之和。用go语言，给定一个整数数组 nums 和一个正整数 k，求所有非空子

福大大架构师每日一题

发布于 2025-08-05 15:10:14

12900

代码可运行

运行总次数：0

代码可运行

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。

解题思路

1. 排序数组：首先将数组 nums 排序。这样我们可以方便地计算每个元素作为最小值和最大值的情况。
2. 组合数学：对于排序后的数组，计算每个元素 nums[i] 作为子序列的最小值和最大值时的贡献。
- • 对于 nums[i] 作为最小值：它出现在子序列中时，子序列的其他元素必须大于或等于 nums[i]（即来自 nums[i..n-1]）。
- • 对于 nums[i] 作为最大值：它出现在子序列中时，子序列的其他元素必须小于或等于 nums[i]（即来自 nums[0..i]）。
3. 动态计算系数：对于每个 nums[i]，我们需要计算它在多少个子序列中作为最小值和最大值。这可以通过组合数来计算：
- • 作为最小值：子序列必须包含 nums[i]，且其他元素从 nums[i+1..n-1] 中选，子序列长度不超过 k。
- • 作为最大值：子序列必须包含 nums[i]，且其他元素从 nums[0..i-1] 中选，子序列长度不超过 k。
4. 快速计算组合数：为了高效计算组合数，预先计算阶乘和逆阶乘数组（模 1000000007），这样可以在 O(1) 时间内计算组合数 C(n, m)。
5. 对称性利用：排序后，nums[i] 作为最小值的贡献与 nums[n-1-i] 作为最大值的贡献是对称的。因此可以同时计算两者的贡献。

具体步骤

1. 排序数组：将 nums 排序，得到 sorted_nums。
2. 初始化阶乘和逆阶乘数组：
- • 预计算 f[i] = i! mod 1000000007。
- • 预计算 invF[i] = (i!)^-1 mod 1000000007（利用费马小定理）。
3. 动态计算系数：
- • 初始化一个系数 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 的子序列的贡献。
4. 累加贡献：
- • 对于每个 i，将 sorted_nums[i] + sorted_nums[n-1-i] 乘以系数 s 累加到结果中。
5. 返回结果：最终结果对 1000000007 取模。

时间和空间复杂度

• 时间复杂度：
- • 排序：O(n log n)。
- • 预计算阶乘和逆阶乘：O(n)。
- • 动态计算系数和累加贡献：O(n)。
- • 总时间复杂度：O(n log n)（排序主导）。
• 空间复杂度：
- • 阶乘和逆阶乘数组：O(n)。
- • 排序：O(log n)（快速排序的递归栈）。
- • 总空间复杂度：O(n)。

Go完整代码如下：

package main

import (
    "fmt"
    "slices"
)

const mod = 1_000_000_007
const mx = 100_000

var f [mx]int    // f[i] = i!
var invF [mx]int// invF[i] = i!^-1

func init() {
    f[0] = 1
    for 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 := 1
    for ; 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 {
        return0
    }
    return f[n] * invF[m] % mod * invF[n-m] % mod
}

func minMaxSums(nums []int, k int) (ans int) {
    slices.Sort(nums)
    s := 1
    for i, x := range nums {
        ans = (ans + s*(x+nums[len(nums)-1-i])) % mod
        s = (s*2 - comb(i, k-1) + mod) % mod
    }
    return
}

func main() {
    nums := []int{5, 0, 6}
    k := 1
    result := minMaxSums(nums, k)
    fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

MOD = 10**9 + 7
MX = 100_000

# 预处理阶乘和逆元
f = [1] * MX
invF = [1] * MX

def pow_mod(x, n):
    res = 1
    while n > 0:
        if n & 1:
            res = res * x % MOD
        x = x * x % MOD
        n >>= 1
    return res

def init():
    for i in range(1, MX):
        f[i] = f[i-1] * i % MOD
    invF[MX-1] = pow_mod(f[MX-1], MOD-2)
    for i in range(MX-1, 0, -1):
        invF[i-1] = invF[i] * i % MOD

def comb(n, m):
    if m > n or m < 0:
        return0
    return f[n] * invF[m] % MOD * invF[n-m] % MOD

def minMaxSums(nums, k):
    nums.sort()
    n = len(nums)
    ans = 0
    s = 1
    for i, x in enumerate(nums):
        ans = (ans + s * (x + nums[n - 1 - i])) % MOD
        s = (s * 2 - comb(i, k-1) + MOD) % MOD
    return ans

if __name__ == "__main__":
    init()
    nums = [5, 0, 6]
    k = 1
    print(minMaxSums(nums, k))