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. 初始化变量和数据结构：

   • 初始化 ans 为 math.MaxInt，用于存储最小正和。
   • 获取数组长度 n。
   • 创建前缀和数组 s，长度为 n+1，s[0] = 0，s[j] 表示 nums[0..j-1] 的和。
   • 创建一个红黑树 cnt，用于存储前缀和及其出现次数，方便快速查询和更新。

2. 遍历数组计算前缀和：

   • 对于每个 j 从 1 到 n：
     • 计算 s[j] = s[j-1] + nums[j-1]。
     • 如果 j < l，跳过后续操作（因为子数组长度至少为 l）。
     • 将 s[j-l] 存入红黑树 cnt，并更新其出现次数（如果已存在则递增，否则初始化为 1）。

3. 查询满足条件的最小正和：

   • 在红黑树 cnt 中查询小于 s[j] 的最大值（即 Floor(s[j] - 1)）。如果存在这样的值 lower，则计算 s[j] - lower.Key 并更新 ans 为较小值。
   • 这一步的目的是找到以 j 结尾的子数组，其长度在 [l, r] 范围内，且和为正的最小值。

4. 维护红黑树的窗口：

   • 如果 j >= r，需要从红黑树中移除 s[j-r]，因为子数组长度不能超过 r。如果该前缀和的计数为 1，则直接移除；否则减少计数。

5. 返回结果：

   • 遍历结束后，如果 ans 仍为 math.MaxInt，说明没有符合条件的子数组，返回 -1；否则返回 ans。

时间复杂度：

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

额外空间复杂度：

• 前缀和数组 s：O(n)。
• 红黑树 cnt：最多存储 O(n) 个元素。
• 总额外空间复杂度：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))
}