2025-06-14：最小正和子数组。用go语言，给定一个整数数组 nums 和两个整数 l 与 r，要求在数组中找到长度介于 l 和 r（含）之间且子数组元素和大于零的连续子数组。你的目标是找到所有符合条件的子数组中，和最小的那一个。

如果存在这样的子数组，返回其最小的正整数和；若找不到，返回 -1。

1 <= nums.length <= 100。

1 <= l <= r <= nums.length。

-1000 <= nums[i] <= 1000。

输入： nums = [1, 2, 3, 4], l = 2, r = 4。

输出： 3。

解释：

子数组 [1, 2] 的长度为 2，和为 3，是所有正和中最小的。因此，答案为 3。

题目来自力扣3364。

分步骤描述过程：

1. 1. 初始化变量和数据结构：
2. o 初始化 ans 为 math.MaxInt，用于存储最小正和。
3. o 获取数组长度 n。
4. o 创建前缀和数组 s，长度为 n+1，s[0] = 0，s[j] 表示 nums[0..j-1] 的和。
5. o 创建一个红黑树 cnt，用于存储前缀和及其出现次数，方便快速查询和更新。
6. 2. 遍历数组计算前缀和：
7. o 对于每个 j 从 1 到 n：
8. o 计算 s[j] = s[j-1] + nums[j-1]。
9. o 如果 j < l，跳过后续操作（因为子数组长度至少为 l）。
10. o 将 s[j-l] 存入红黑树 cnt，并更新其出现次数（如果已存在则递增，否则初始化为 1）。
11. 3. 查询满足条件的最小正和：
12. o 在红黑树 cnt 中查询小于 s[j] 的最大值（即 Floor(s[j] - 1)）。如果存在这样的值 lower，则计算 s[j] - lower.Key 并更新 ans 为较小值。
13. o 这一步的目的是找到以 j 结尾的子数组，其长度在 [l, r] 范围内，且和为正的最小值。
14. 4. 维护红黑树的窗口：
15. o 如果 j >= r，需要从红黑树中移除 s[j-r]，因为子数组长度不能超过 r。如果该前缀和的计数为 1，则直接移除；否则减少计数。
16. 5. 返回结果：
17. o 遍历结束后，如果 ans 仍为 math.MaxInt，说明没有符合条件的子数组，返回 -1；否则返回 ans。

时间复杂度：

• o 遍历数组：O(n)。
• o 红黑树操作（插入、删除、查询）：每次操作 O(log n)，最多 O(n) 次操作。
• o 总时间复杂度：O(n log n)。

额外空间复杂度：

• o 前缀和数组 s：O(n)。
• o 红黑树 cnt：最多存储 O(n) 个元素。
• o 总额外空间复杂度：O(n)。

Go完整代码如下：

.

package main

import (
    "fmt"
    "math"
    "github.com/emirpasic/gods/v2/trees/redblacktree"
)

func minimumSumSubarray(nums []int, l, r int)int {
    ans := math.MaxInt
    n := len(nums)
    s := make([]int, n+1)
    cnt := redblacktree.New[int, int]()
    for j := 1; j <= n; j++ {
        s[j] = s[j-1] + nums[j-1]
        if j < l {
            continue
        }
        c, _ := cnt.Get(s[j-l])
        cnt.Put(s[j-l], c+1)
        if lower, ok := cnt.Floor(s[j] - 1); ok {
            ans = min(ans, s[j]-lower.Key)
        }
        if j >= r {
            v := s[j-r]
            c, _ := cnt.Get(v)
            if c == 1 {
                cnt.Remove(v)
            } else {
                cnt.Put(v, c-1)
            }
        }
    }
    if ans == math.MaxInt {
        return-1
    }
    return ans
}


func main() {
    nums := []int{1, 2, 3, 4}
    l := 2
    r := 4
    fmt.Println(minimumSumSubarray(nums,l,r))
}

·

我们相信Go语言和算法为普通开发者提供了困境的“面试利器”，并致力于分享全面的编程知识。在这里，您可以找到最新的Go语言教程、算法解析、提升面试竞争力的秘籍以及行业动态。

欢迎关注“福大规模架构师每日一题”，让 Go 语言和算法助力您的职业发展

·