給定正整數陣列
nums和正整數target，回傳和 >=target的最短連續子陣列長度。若不存在則回傳 0。
Example:
Input: target = 7, nums = [2,3,1,2,4,3] Output: 2（子陣列 [4,3] 和為 7）
Intuition
TIP
核心思路：可變大小滑動視窗，右指針擴展累加總和，當總和 >= target 時嘗試收縮左邊界找最短長度。
- 所有元素為正數，所以視窗越大總和越大 — 單調性保證滑動視窗的正確性
- 右指針持續擴展，左指針在滿足條件時盡量收縮
- 每次滿足條件時更新最小長度
Approaches
1. Brute Force — O(n²) / O(1)
- Idea: 嘗試所有起點，向右累加直到 >= target
- Time:
O(n²) - Space:
O(1)
Brute Force Code
class Solution {
fun minSubArrayLen(target: Int, nums: IntArray): Int {
var result = Int.MAX_VALUE
for (i in nums.indices) {
var sum = 0
for (j in i until nums.size) {
sum += nums[j]
if (sum >= target) {
result = minOf(result, j - i + 1)
break
}
}
}
return if (result == Int.MAX_VALUE) 0 else result
}
}⭐ 2. Sliding Window (variable size) — O(n) / O(1)
- Idea: 維護視窗總和，右指針擴展、左指針收縮
- Time:
O(n)- 左右指針各最多遍歷 n 次 - Space:
O(1)
class Solution {
fun minSubArrayLen(target: Int, nums: IntArray): Int {
var left = 0
var sum = 0
var result = Int.MAX_VALUE
for (right in nums.indices) {
sum += nums[right]
while (sum >= target) {
result = minOf(result, right - left + 1)
sum -= nums[left]
left++
}
}
return if (result == Int.MAX_VALUE) 0 else result
}
}WARNING
此題元素全為正數才能用滑動視窗。若有負數，需要用 Prefix Sum + TreeMap 等方法。
🔑 Takeaways
- Pattern: 可變大小滑動視窗（找最短滿足條件的子陣列）
- Key trick: 當視窗滿足條件時用 while 持續收縮左邊界，確保找到最小長度；正數陣列的單調性是此方法的前提