题目描述

给你一个整数数组 nums 和 两个 整数 l 和 r。你的任务是找到一个长度在 l 和 r 之间（包含）且和大于 0 的 子数组 的 最小 和。

返回满足条件的子数组的 最小 和。如果不存在这样的子数组，则返回 -1。

子数组 是数组中的一个连续 非空 元素序列。

样例

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

输出： 1

解释：

长度在 l = 2 和 r = 3 之间且和大于 0 的子数组有：

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

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

输出： -1

解释：

不存在长度在 l 和 r 之间且和大于 0 的子数组。因此，答案为 -1。

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

输出： 3

解释：

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

限制

• 1 <= nums.length <= 100
• 1 <= l <= r <= nums.length
• -1000 <= nums[i] <= 1000

算法

(前缀和，有序集) $O(n \log n)$

1. 求出原数组的前缀和数组。
2. 从第 $l$ 个位置开始遍历，假设当前位置的前缀和为 $x$，希望能快速找到区间 $[i - r, i - l]$ 内严格小于 $x$ 的前缀和。
3. 可以使用有序集动态维护区间内的值，通过 lower_bound 的操作快速找到符合要求的前缀和做差值，更新答案。

时间复杂度

• 预处理前缀和的时间复杂度为 $O(n)$。
• 遍历数组，每次都需要操作有序集，并在有序集上进行二分操作，单次的时间复杂度为 $O(\log n)$。
• 故总时间复杂度为 $O(n \log n)$。

空间复杂度

• 需要 $O(n)$ 的额外空间存储有序集。

C++ 代码

class Solution {
public:
    int minimumSumSubarray(vector<int>& nums, int l, int r) {
        const int n = nums.size();

        nums.insert(nums.begin(), 0);
        for (int i = 1; i <= n; i++)
            nums[i] += nums[i - 1];

        multiset<int> h;
        int ans = INT_MAX;
        for (int i = l; i <= n; i++) {
            h.insert(nums[i - l]);

            auto it = h.lower_bound(nums[i]);
            if (it != h.begin()) {
                --it;
                ans = min(ans, nums[i] - *it);
            }

            if (i >= r)
                h.erase(h.find(nums[i - r]));
        }

        return ans == INT_MAX ? -1 : ans;
    }
};