第425场周赛题解：最小正和子数组

最小正和子数组

1、题目描述

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

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

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

2、解题思路

1. 滑动窗口：
   • 使用滑动窗口遍历数组，可以高效地计算子数组和。
   • 在窗口长度范围内逐一检查是否满足条件。
2. 暴力双层循环优化：
   • 第一层循环选择子数组的左边界。
   • 第二层循环从左边界延伸到右边界，并动态累加子数组的和，避免重复计算。
3. 判断合法性：
   • 每当子数组的长度满足 [l,r] 且和大于 0 时，记录其和。
   • 更新符合条件的最小和。
4. 最终结果：
   • 如果遍历完数组仍未找到符合条件的子数组，返回 −1 。

3、代码实现

int minimumSumSubarray(vector<int>& nums, int l, int r) {
    int n = nums.size();
    int minSum = INT_MAX; // 初始化最小和为无穷大

    int left = 0; // 滑动窗口的左边界

    // 遍历数组的每个起始点作为窗口的左边界
    while (left < n) {
        int right = left; // 窗口的右边界从左边界开始
        int currentSum = 0; // 当前窗口的和

        // 扩展右边界，直到窗口长度超过 r 或到达数组末尾
        while (right < n && right - left + 1 <= r) {
            currentSum += nums[right]; // 累加当前窗口的和
            
            // 判断当前窗口是否满足长度 [l, r] 且和大于 0
            if (right - left + 1 >= l && currentSum > 0) {
                minSum = min(minSum, currentSum); // 更新最小和
            }

            ++right; // 扩展右边界
        }

        ++left; // 移动左边界
    }

    // 如果没有符合条件的子数组，返回 -1；否则返回最小和
    return minSum == INT_MAX ? -1 : minSum;
}

4、复杂度

时间复杂度分析

• 外层循环：左边界最多遍历 n 次。
• 内层循环：右边界最多遍历 r 次（窗口长度限制为 r）。
• 总复杂度：O(n⋅r)，其中 r 是窗口的最大长度。

空间复杂度分析

• 仅使用常数额外空间，空间复杂度为 O(1) 。