3364.最小正和子数组：暴力模拟 O(nr)

【LetMeFly】3364.最小正和子数组：暴力模拟 O(nr)

力扣题目链接：https://leetcode.cn/problems/minimum-positive-sum-subarray/

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

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

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

 

示例 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。

示例 2：

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

输出： -1

解释：

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

示例 3：

输入： 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

也不是那么暴力

解题方法：模拟

第一层循环用变量$i$枚举子数组起点，第二层循环用变量$len$枚举子数组长度：

$len$从$0$枚举到$r$并累加子数组和，当$len \geq l$时，若子数组和$\gt 0$则更新答案最小值

• 时间复杂度$O(nr)$
• 空间复杂度$O(1)$

AC代码

C++

/*
 * @LastEditTime: 2026-11-14 13:01:20
 */
class Solution {
public:
    int minimumSumSubarray(vector<int>& nums, int l, int r) {
        int ans = 1000000;
        for (int i = 0, n = nums.size(); i < n; i++) {
            int cnt = 0;
            for (int len = 0; len < l - 1 && i + len < n; len++) {
                cnt += nums[i + len];
            }
            for (int len = l - 1; len < r && i + len < n; len++) {
                cnt += nums[i + len];
                if (cnt > 0) {
                    ans = min(ans, cnt);
                }
            }
        }
        return ans == 1000000 ? -1 : ans;
    }
};

实际代码实现中$len$更像是偏移量，因为$len$是从$0$到$r-1$。

End

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

千篇源码题解已开源