What is the key pattern for solving Minimum Positive Sum Subarray?

The key pattern is sliding window with running sum updates, checking all subarrays of length between l and r efficiently.

Can I use a prefix sum array to optimize this problem?

Yes, prefix sums allow constant-time computation of subarray sums, which is efficient when iterating over all valid subarray lengths.

What should I return if no subarray has a positive sum?

Return -1, as specified in the problem, ensuring the solution handles negative-heavy arrays correctly.

Does the solution handle arrays with all negative numbers?

Yes, the sliding window or prefix sum approach correctly identifies that no positive sum exists and returns -1.

Is the sliding window approach always faster than brute-force here?

For small constraints, brute-force is acceptable, but sliding window reduces repeated summation and aligns with the intended pattern.

#3364

Easy

auto_awesome滑动窗口（状态滚动更新）

LeetCode 题解工作台

最小正和子数组

给你一个整数数组 nums 和两个整数 l 和 r 。你的任务是找到一个长度在 l 和 r 之间（包含）且和大于 0 的子数组的最小和。返回满足条件的子数组的最小和。如果不存在这样的子数组，则返回 -1。子数组是数组中的一个连续非空元素序列。示例 1：输入： nums …

数组滑动窗口前缀和

题目描述

给你一个整数数组 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

lightbulb

解题思路

方法一：枚举

我们可以枚举子数组的左端点 $i$ ，然后在 $[i, n)$ 的区间内从左往右枚举右端点 $j$ ，计算区间 $[i, j]$ 的和 $s$ ，如果 $s$ 大于 0 且区间长度在 $[l, r]$ 之间，我们就更新答案。

最后，如果答案仍然是初始值，说明没有找到符合条件的子数组，返回 $-1$ ，否则返回答案。

时间复杂度 $O(n^2)$ ，其中 $n$ 是数组 $\textit{nums}$ 的长度。空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

10

11

12

class Solution:
    def minimumSumSubarray(self, nums: List[int], l: int, r: int) -> int:
        n = len(nums)
        ans = inf
        for i in range(n):
            s = 0
            for j in range(i, n):
                s += nums[j]
                if l <= j - i + 1 <= r and s > 0:
                    ans = min(ans, s)
        return -1 if ans == inf else ans

speed

复杂度分析

指标	值
时间	complexity is O(n*r) in the worst case, iterating over each start index and length up to r. Space complexity is O(n) if using prefix sums or O(1) with a purely running sum approach.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Check if the candidate recognizes that naive nested loops are sufficient due to constraints.
question_mark
Listen for understanding of sliding window vs prefix sum trade-offs.
question_mark
See if the candidate considers negative numbers affecting positive sum checks.

warning

常见陷阱

外企场景

error
Assuming all subarrays have positive sums and not checking for -1 return.
error
Incorrectly handling subarrays shorter than l or longer than r.
error
Recomputing sums from scratch instead of using running sums or prefix sums.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Find maximum positive sum subarray within a length range instead of minimum.
arrow_right_alt
Return the actual subarray with minimum positive sum rather than just the sum.
arrow_right_alt
Apply the same approach to a circular array, adjusting sliding window logic.

help

常见问题

外企场景

继续练习

#3347 执行操作后元素的最高频率 II #3346 执行操作后元素的最高频率 I #3413 收集连续 K 个袋子可以获得的最多硬币数量