[Leetcode解題] 3364. Minimum Positive Sum Subarray
15 November 2026
easy
array
prefix-sum
sliding-window
題目
3364. Minimum Positive Sum Subarray
給定一個整數陣列 nums 以及兩個整數 l 與 r。
請找出一個連續子陣列,滿足以下條件:
- 子陣列長度介於
l與r之間(即 $l \le \text{length} \le r$)。 - 子陣列所有元素的和嚴格大於 0($\text{sum} > 0$)。
在所有符合條件的子陣列中,回傳其最小的總和。如果不存在任何符合條件的子陣列,請回傳 -1。
題目限制:
- $1 \le \text{nums.length} \le 100$
- $1 \le l \le r \le \text{nums.length}$
- $-1000 \le \text{nums}[i] \le 1000$
解題思路
1. 題目需求與限制分析
題目要求尋找長度落在區間 $[l, r]$ 內,且總和嚴格大於 0 的子陣列之最小總和。
陣列長度限制 $n \le 100$,規模非常小。如果我們枚舉所有合法的起點與終點,總共的區間數大約為: \(O(n \cdot (r - l + 1)) \le O(n^2)\) 當 $n = 100$ 時,最多僅約 5,000 種子陣列組合,因此使用前綴和(Prefix Sum)進行枚舉即可在極短時間內完成。
2. 利用前綴和 $O(1)$ 取得區間和
如果每次計算子陣列和都透過迴圈從頭加到尾,時間複雜度會多出一個維度。為了加速計算,我們先建立長度為 $n + 1$ 的前綴和陣列 presum:
presum[0] = 0presum[k] = nums[0] + nums[1] + ... + nums[k - 1]
對於任意左開右閉或從索引 $i$ 開始、到索引 $j - 1$ 結束的連續子陣列 nums[i..j-1](長度為 $j - i$):
\(\text{current\_sum} = \text{presum}[j] - \text{presum}[i]\)
只需進行一次減法即可取得區間總和。
3. 枚舉所有符合長度限制的子陣列
- 外層迴圈枚舉子陣列的起點 $i \in [0, n - 1]$。
- 內層迴圈枚舉結尾位置 $j$。因為子陣列長度必須介於 $l$ 與 $r$ 之間,所以長度 $len = j - i$ 必須符合 $l \le len \le r$,即: \(j \in [i + l, \min(i + r, n)]\)
- 計算當前區間總和 $\text{current_sum} = \text{presum}[j] - \text{presum}[i]$。
- 若 $\text{current_sum} > 0$,則更新答案最小值: \(\text{min\_val} = \min(\text{min\_val}, \text{current\_sum})\)
走訪完所有可能後,若 min_val 仍為初始值(如無窮大),代表沒有任何正數總和的子陣列,回傳 -1;否則回傳 min_val。
演算法步驟
- 計算陣列長度 $n = \text{len}(nums)$,建立長度為 $n + 1$ 的前綴和陣列
presum。 - 走訪 $nums$,依序計算前綴和:
presum[i + 1] = presum[i] + nums[i]。 - 初始化答案
min_val為正無窮大($\infty$)。 - 雙層迴圈枚舉:
- 起點 $i$ 從 $0$ 到 $n - 1$。
- 終點 $j$ 從 $i + l$ 到 $\min(i + r, n)$。
- 計算區間和
current_sum = presum[j] - presum[i]。 - 若
current_sum > 0,則令min_val = min(min_val, current_sum)。
- 若
min_val仍為無窮大,回傳-1;否則回傳min_val。
C++ 實作
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;
class Solution {
public:
int minimumSumSubarray(vector<int>& nums, int l, int r) {
int n = nums.size();
vector<int> presum(n + 1, 0);
for (int i = 0; i < n; i++) {
presum[i + 1] = presum[i] + nums[i];
}
int min_val = INT_MAX;
for (int i = 0; i < n; i++) {
int end = min(i + r, n);
for (int j = i + l; j <= end; j++) {
int current_sum = presum[j] - presum[i];
if (current_sum > 0) {
min_val = min(min_val, current_sum);
}
}
}
return min_val == INT_MAX ? -1 : min_val;
}
};
Python 實作
from typing import List
class Solution:
def minimumSumSubarray(self, nums: List[int], l: int, r: int) -> int:
n = len(nums)
presum = [0] * (n + 1)
for i in range(n):
presum[i + 1] = presum[i] + nums[i]
min_val = float('inf')
# O(n * (r - l + 1))
for i in range(n):
for j in range(i + l, min(i + r, n) + 1):
current_sum = presum[j] - presum[i]
if current_sum > 0:
min_val = min(min_val, current_sum)
return min_val if min_val != float('inf') else -1
複雜度分析
令 $n = \text{nums.length}$,以及長度範圍跨度 $m = r - l + 1$。
- 時間複雜度:$O(n \cdot m)$。建立前綴和陣列耗費 $O(n)$。枚舉區間起點共 $n$ 個,對於每個起點,終點檢查最多 $r - l + 1$ 個,每次以 $O(1)$ 算出區間和。最壞情況下 $m \le n$,整體時間複雜度為 $O(n^2)$。因 $n \le 100$,運算次數在 $10^4$ 以內,執行非常迅速。
- 空間複雜度:$O(n)$。需要一個大小為 $n + 1$ 的陣列儲存前綴和。
常見注意事項
- 正數限制:題目要求總和必須嚴格大於 0(
current_sum > 0),總和小於或等於 0 的子陣列均不能列入考慮。 - 邊界與長度:內層迴圈終點上界為 $\min(i + r, n)$,避免陣列索引越界。
- 無解回傳:若遍歷所有合法區間後均未找到大於 0 的總和,依題意回傳
-1。