209. 长度最小的子数组
题目描述
输入正整数 target 和一个由 n 个正整数组成的数组 nums。
在所有元素和不小于 target 的连续子数组里，找出长度最短的一个，返回它的长度。
如果没有任何连续子数组满足条件，返回 0。
示例 1
输入：target = 7, nums = [2,3,1,2,4,3] 输出：2
解释：[4,3] 的和为 7，长度 2 是最短的。
示例 2
输入：target = 4, nums = [1,4,4] 输出：1
解释：单个元素 4 已经满足条件。
示例 3
输入：target = 11, nums = [1,1,1,1,1,1,1,1] 输出：0
解释：整个数组的和只有 8，小于 11，没有满足条件的子数组。
数据范围
1 <= target <= 10^91 <= nums.length <= 10^51 <= nums[i] <= 10^4
进阶：如果你已经写出 O(n) 的做法，再试试设计一个 O(n log(n)) 的做法。
解题思路：滑动窗口
所有元素为正，前缀和严格递增，这是可以二分的根本原因：对每个左端可在前缀和上二分出最短右端，O(n log n)。同样的单调性还允许更快的滑动窗口：右端 right 逐个加入，一旦窗口和 s >= target，就记录长度并不断弹出左端，直到 s < target。左端只向右走，合计 O(n)。
为什么正确
每次内层循环开始前，对当前 right，[left, right] 是左端不小于之前任何合法左端的候选；被弹出的左端已经找到了它能形成的最短合法窗口。
复杂度分析
滑动窗口时间 O(n)、空间 O(1)；前缀和 + 二分 O(n log n)。
易错点
内层要用 while 而不是 if；ans 初值用 n+1 或无穷大，最后要把“未更新”转成 0。只有元素全为正时这个方法才成立。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def minSubArrayLen(self, target: int, nums: List[int]) -> int:
ans = len(nums) + 1
s = left = 0
for right, x in enumerate(nums):
s += x
while s >= target:
ans = min(ans, right - left + 1)
s -= nums[left]
left += 1
return ans if ans <= len(nums) else 0class Solution {
public int minSubArrayLen(int target, int[] nums) {
int n = nums.length, ans = n + 1;
int s = 0, left = 0;
for (int right = 0; right < n; right++) {
s += nums[right];
while (s >= target) {
ans = Math.min(ans, right - left + 1);
s -= nums[left];
left++;
}
}
return ans <= n ? ans : 0;
}
}class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int n = nums.size(), ans = n + 1;
int s = 0, left = 0;
for (int right = 0; right < n; right++) {
s += nums[right];
while (s >= target) {
ans = min(ans, right - left + 1);
s -= nums[left];
left++;
}
}
return ans <= n ? ans : 0;
}
};func minSubArrayLen(target int, nums []int) int {
n := len(nums)
ans := n + 1
s, left := 0, 0
for right, x := range nums {
s += x
for s >= target {
ans = min(ans, right-left+1)
s -= nums[left]
left++
}
}
if ans <= n {
return ans
}
return 0
}var minSubArrayLen = function(target, nums) {
const n = nums.length;
let ans = n + 1;
let s = 0, left = 0;
for (let right = 0; right < n; right++) {
s += nums[right];
while (s >= target) {
ans = Math.min(ans, right - left + 1);
s -= nums[left];
left++;
}
}
return ans <= n ? ans : 0;
};function minSubArrayLen(target: number, nums: number[]): number {
const n = nums.length;
let ans = n + 1;
let s = 0, left = 0;
for (let right = 0; right < n; right++) {
s += nums[right];
while (s >= target) {
ans = Math.min(ans, right - left + 1);
s -= nums[left];
left++;
}
}
return ans <= n ? ans : 0;
}其他解法
两种解法都依赖“元素全为正数”：前缀和二分利用前缀和单调，对每个起点独立二分；滑动窗口利用左右端点都只向右移动，整体 O(n)。
解法 2：前缀和 + 二分查找 时间 O(n log n)，空间 O(n)
先算前缀和 pre，pre[i] 是前 i 个数的和。因为所有数都是正数，pre 严格递增。枚举子数组的起点 i，在 pre 中二分查找第一个满足 pre[j] ≥ pre[i] + target 的下标 j，子数组 [i, j) 的长度 j - i 就是以 i 开头时的最短长度，取所有起点中的最小值。
对应进阶要求的 O(n log n) 解法，展示了“前缀和单调就能二分”的思路。比滑动窗口多一个 log 因子和 O(n) 空间。
from bisect import bisect_left
from itertools import accumulate
from typing import List
class Solution:
def minSubArrayLen(self, target: int, nums: List[int]) -> int:
n = len(nums)
pre = [0] + list(accumulate(nums))
ans = n + 1
for i in range(n):
j = bisect_left(pre, pre[i] + target)
if j <= n:
ans = min(ans, j - i)
return ans if ans <= n else 0class Solution {
public int minSubArrayLen(int target, int[] nums) {
int n = nums.length;
long[] pre = new long[n + 1];
for (int i = 0; i < n; i++) pre[i + 1] = pre[i] + nums[i];
int ans = n + 1;
for (int i = 0; i < n; i++) {
long need = pre[i] + target;
int lo = i + 1, hi = n + 1;
while (lo < hi) {
int mid = (lo + hi) >>> 1;
if (pre[mid] >= need) hi = mid;
else lo = mid + 1;
}
if (lo <= n) ans = Math.min(ans, lo - i);
}
return ans <= n ? ans : 0;
}
}class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int n = nums.size();
vector<long long> pre(n + 1, 0);
for (int i = 0; i < n; i++) pre[i + 1] = pre[i] + nums[i];
int ans = n + 1;
for (int i = 0; i < n; i++) {
int j = lower_bound(pre.begin(), pre.end(), pre[i] + target) - pre.begin();
if (j <= n) ans = min(ans, j - i);
}
return ans <= n ? ans : 0;
}
};func minSubArrayLen(target int, nums []int) int {
n := len(nums)
pre := make([]int, n+1)
for i, x := range nums {
pre[i+1] = pre[i] + x
}
ans := n + 1
for i := 0; i < n; i++ {
j := sort.SearchInts(pre, pre[i]+target)
if j <= n {
ans = min(ans, j-i)
}
}
if ans <= n {
return ans
}
return 0
}var minSubArrayLen = function(target, nums) {
const n = nums.length;
const pre = new Array(n + 1).fill(0);
for (let i = 0; i < n; i++) pre[i + 1] = pre[i] + nums[i];
let ans = n + 1;
for (let i = 0; i < n; i++) {
const need = pre[i] + target;
let lo = i + 1, hi = n + 1;
while (lo < hi) {
const mid = (lo + hi) >> 1;
if (pre[mid] >= need) hi = mid;
else lo = mid + 1;
}
if (lo <= n) ans = Math.min(ans, lo - i);
}
return ans <= n ? ans : 0;
};function minSubArrayLen(target: number, nums: number[]): number {
const n = nums.length;
const pre: number[] = new Array(n + 1).fill(0);
for (let i = 0; i < n; i++) pre[i + 1] = pre[i] + nums[i];
let ans = n + 1;
for (let i = 0; i < n; i++) {
const need = pre[i] + target;
let lo = i + 1, hi = n + 1;
while (lo < hi) {
const mid = (lo + hi) >> 1;
if (pre[mid] >= need) hi = mid;
else lo = mid + 1;
}
if (lo <= n) ans = Math.min(ans, lo - i);
}
return ans <= n ? ans : 0;
};