LogicStack-LeetCode 题解:209. 长度最小的子数组(中等)——前缀和 + 二分与滑动窗口双解法深度拆解
LogicStack-LeetCode 题解:209. 长度最小的子数组(中等)——前缀和 + 二分与滑动窗口双解法深度拆解
本文是「刷穿 LeetCode」系列第 No.209 篇的技术详解,基于 LeetCode/201-210/209. 长度最小的子数组(中等).md 原文档展开。全篇围绕"正数数组 + 和 ≥ target 的最短连续子数组"这一经典模型,完整讲解前缀和 + 二分与滑动窗口两套解法在 Java、C++、Python、TypeScript 四种语言下的实现,并结合仓库中 剑指 Offer II 008(同题变体)、1208. 尽可能使字符串相等 以及 滑动窗口索引、前缀和索引 给出体系化的延伸视角。读完本文,你将同时掌握"如何用二段性把 O(n²) 枚举优化到 O(n log n)"与"如何用单调性做到严格 O(n)"两种思维路径,并能直接套用代码模板解决同类最短/最长合法区间问题。
一、题目描述与关键约束
给定一个含有 n 个正整数的数组 nums 和一个正整数 target,找出数组中满足其和 ≥ target 的长度最小的连续子数组 [nums_l, nums_{l+1}, ..., nums_r],返回其长度;若不存在符合条件的子数组,返回 0。
示例 1
输入:target = 7, nums = [2,3,1,2,4,3]
输出:2
解释:子数组 [4,3] 是该条件下的长度最小的子数组。
示例 2
输入:target = 4, nums = [1,4,4]
输出:1
示例 3
输入:target = 11, nums = [1,1,1,1,1,1,1,1]
输出:0
提示(约束范围)
1 <= target <= 10^91 <= nums.length <= 10^51 <= nums[i] <= 10^5
约束分析(本题的破题关键)
n <= 10^5决定了朴素"枚举所有子数组"的 O(n²) 做法(单个样本计算量达 10¹⁰ 量级)必然超时,必须寻找 O(n log n) 乃至 O(n) 的解法。nums[i] >= 1(全为正数)意味着前缀和数组严格单调递增,这是「前缀和 + 二分」成立的前提;- 同样因为全为正数,窗口内的和随窗口右端点右移单调不减,这是「滑动窗口」能够贪心收缩左端点的前提。
二、方法一:前缀和 + 二分(O(n log n))
2.1 核心思路
利用 nums[i] 的数据范围为 [1, 10^5],可知前缀和数组满足「单调递增」。
具体推导如下:
- 预处理前缀和数组
sum:下标从1开始,sum[i]表示前i个元素的和,即sum[i] = sum[i-1] + nums[i-1]。 - 固定右端点:遍历到
nums[i]时,其对应的前缀和值为s = sum[i]。将nums[i]视为子数组右端点后,问题转化为:在前缀和数组下标[0, i]范围内,找到满足「值小于等于s - t」的最大下标r,这个r充当子数组左端点的前一个位置,则合法子数组为[r+1, i],长度为i - r。 - 二段性判定:由于前缀和数组单调递增,
sum[0..i]中"≤ s - t"的部分与"> s - t"的部分天然形成两段,可以用「二分」定位分界点。
这里有一个容易混淆的细节:题目要求 sum[i] - sum[r] >= t,即 sum[r] <= sum[i] - t。我们找的是满足该不等式条件下最大的 r(左端点尽量靠右),这样得到的窗口长度 i - r 才是当前右端点下最短的合法窗口。
2.2 二分边界与"找最大下标"模板
因为要找的是「满足条件的最右位置」,二分模板采用**右边界型(upper bound 变体)**写法:mid = (l + r + 1) >> 1,当 sum[mid] <= d 时收缩左边界 l = mid,否则收缩右边界 r = mid - 1。
l的初值为0,r的初值为i,保证搜索范围覆盖前缀和数组的全部合法下标;+1的目的是避免l与r相邻时陷入死循环(l + r >> 1在l = r - 1时会得到l本身,导致左边界永远无法前进);- 二分结束后还需用
if (sum[r] <= d)做一次兜底校验:当target大于整个前缀和(即当前右端点无法构成任何合法窗口)时,r会停在0,此时需要跳过更新答案。
2.3 四种语言代码
Java
class Solution {
public int minSubArrayLen(int t, int[] nums) {
int n = nums.length, ans = n + 10;
int[] sum = new int[n + 10];
for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + nums[i - 1];
for (int i = 1; i <= n; i++) {
int d = sum[i] - t;
int l = 0, r = i;
while (l < r) {
int mid = l + r + 1 >> 1;
if (sum[mid] <= d) l = mid;
else r = mid - 1;
}
if (sum[r] <= d) ans = Math.min(ans, i - r);
}
return ans == n + 10 ? 0 : ans;
}
}
C++
class Solution {
public:
int minSubArrayLen(int t, vector<int>& nums) {
int n = nums.size(), ans = n + 10;
vector<int> sum(n + 10, 0);
for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + nums[i - 1];
for (int i = 1; i <= n; i++) {
int d = sum[i] - t;
int l = 0, r = i;
while (l < r) {
int mid = (l + r + 1) >> 1;
if (sum[mid] <= d) l = mid;
else r = mid - 1;
}
if (sum[r] <= d) ans = min(ans, i - r);
}
return ans == n + 10 ? 0 : ans;
}
};
Python
class Solution:
def minSubArrayLen(self, t: int, nums: List[int]) -> int:
n, ans = len(nums), len(nums) + 10
s = [0] * (n + 10)
for i in range(1, n + 1):
s[i] = s[i - 1] + nums[i - 1]
for i in range(1, n + 1):
d = s[i] - t
l, r = 0, i
while l < r:
mid = (l + r + 1) // 2
if s[mid] <= d:
l = mid
else:
r = mid - 1
if s[r] <= d:
ans = min(ans, i - r)
return 0 if ans == n + 10 else ans
TypeScript
function minSubArrayLen(t: number, nums: number[]): number {
let n = nums.length, ans = n + 10;
const sum = new Array(n + 10).fill(0);
for (let i = 1; i <= n; i++) sum[i] = sum[i - 1] + nums[i - 1];
for (let i = 1; i <= n; i++) {
const d = sum[i] - t;
let l = 0, r = i;
while (l < r) {
const mid = l + r + 1 >> 1;
if (sum[mid] <= d) l = mid;
else r = mid - 1;
}
if (sum[r] <= d) ans = Math.min(ans, i - r);
}
return ans == n + 10 ? 0 : ans;
};
2.4 复杂度分析
- 时间复杂度:预处理前缀和数组为 O(n);随后遍历
n个右端点,每个端点做一次 O(log n) 二分,合计 O(n log n)。整体为 O(n log n)。 - 空间复杂度:额外使用长度为
n + 10的前缀和数组,为 O(n)。
仓库佐证:仓库中的 剑指 Offer II 008. 和大于等于 target 的最短子数组(中等).md 与本题完全同题,其给出的正是这份"前缀和 + 二分"代码(Tag 标注为「前缀和」、「二分」),可作为本题在另一题库中的对照题解。
三、方法二:滑动窗口(O(n))
3.1 核心思路
前缀和 + 二分的复杂度为 O(n log n),但还有更优的 O(n) 做法——滑动窗口(双指针)。
在一次遍历过程中:
- 使用
j和i分别代表窗口的左右端点(i为右端点、j为左端点),变量c用于记录窗口内的数值总和; - 遍历过程就是右端点
i不断右移的过程:每次将nums[i]累加到c上; - 累加后检查:若左端点右移一位(即移出
nums[j])后,窗口总和仍能满足「≥ target」,那么就让左端点j右移,同时从c中减去nums[j]。
这样做的效果是:对于每个固定的右端点 i,我们总能得到下标最大的合法左端点 j(若存在),即当前右端点下最短的合法窗口。遍历过程中所有合法窗口长度 i - j + 1 的最小值即为答案。
3.2 为什么这样贪心是安全的(单调性保证)
因为数组元素全为正数,c 随 i 增大单调不减。当右端点 i 确定后,只要 c - nums[j] >= t 仍成立,就说明移除最左侧元素后窗口依然合法——此时窗口更短,必然优于不移动的窗口,因此可以放心收缩左端点。这个"能收缩就收缩"的策略不会漏掉最优解,因为最优解的右端点也一定在某个 i 处被枚举到,且在该 i 下,贪心得到的 j 一定是所有合法左端点中下标最大的(窗口最短的)。
3.3 四种语言代码
Java
class Solution {
public int minSubArrayLen(int t, int[] nums) {
int n = nums.length, ans = n + 10;
for (int i = 0, j = 0, c = 0; i < n; i++) {
c += nums[i];
while (j < i && c - nums[j] >= t) c -= nums[j++];
if (c >= t) ans = Math.min(ans, i - j + 1);
}
return ans > n ? 0 : ans;
}
}
C++
class Solution {
public:
int minSubArrayLen(int t, vector<int>& nums) {
int n = nums.size(), ans = n + 10;
for (int i = 0, j = 0, c = 0; i < n; i++) {
c += nums[i];
while (j < i && c - nums[j] >= t) c -= nums[j++];
if (c >= t) ans = min(ans, i - j + 1);
}
return ans > n ? 0 : ans;
}
};
Python
class Solution:
def minSubArrayLen(self, t: int, nums: List[int]) -> int:
n, ans = len(nums), len(nums) + 10
j, c = 0, 0
for i in range(n):
c += nums[i]
while j < i and c - nums[j] >= t:
c -= nums[j]
j += 1
if c >= t:
ans = min(ans, i - j + 1)
return 0 if ans > n else ans
TypeScript
function minSubArrayLen(t: number, nums: number[]): number {
let n = nums.length, ans = n + 10;
for (let i = 0, j = 0, c = 0; i < n; i++) {
c += nums[i];
while (j < i && c - nums[j] >= t) c -= nums[j++];
if (c >= t) ans = Math.min(ans, i - j + 1);
}
return ans > n ? 0 : ans;
};
3.4 代码细节解读
while (j < i && c - nums[j] >= t):加j < i保护,保证窗口至少保留一个元素,避免左端点越过右端点;if (c >= t)再更新答案:当整个前缀和都凑不够target时,当前窗口不合法,不参与答案更新;ans > n ? 0 : ans(Java/C++ 版):若从未找到合法窗口,ans保持初始值n + 10,返回0;- 该写法是"先尝试收缩、再统计长度"的顺序,与"先统计长度、再收缩"的常规写法结果等价,但逻辑上更紧凑——它直接维护了每个右端点下最短的合法窗口。
3.5 复杂度分析
- 时间复杂度:
i与j各至多移动n次,整体为 O(n); - 空间复杂度:仅使用常数个变量(
ans、j、c),为 O(1)。
四、两种解法对比:二段性 vs 单调性
| 维度 | 前缀和 + 二分 | 滑动窗口 |
|---|---|---|
| 依赖的性质 | 前缀和数组单调递增(二段性) | 窗口和随端点移动单调不减(单调性) |
| 时间复杂度 | O(n log n) | O(n) |
| 空间复杂度 | O(n)(前缀和数组) | O(1) |
| 适用前提 | 数组元素非负,前缀和可二分 | 数组元素非负,窗口收缩具有单调性 |
| 推荐场景 | 需要复用前缀和、或后续还要做区间查询 | 追求最优复杂度、代码最简 |
两道解法本质上是同一个单调性假设在"预计算"与"在线维护"两条路径上的体现:前缀和把区间和变成 O(1) 查询,再用二分压榨单调性;滑动窗口则直接用双指针在遍历中维护窗口和,省去预计算空间。
从仓库索引可以看到,这两种套路在本仓库中均被反复使用:
- 滑动窗口.md 汇总了 30+ 道滑动窗口题目,从 3. 无重复字符的最长子串、76. 最小覆盖子串 到 424. 替换后的最长重复字符、1438. 绝对差不超过限制的最长连续子数组 等,均是本题"固定右端点 + 贪心收缩左端点"思想的直接延伸;
- 前缀和.md 则将 209 题收录于前缀和专题,与 560. 和为 K 的子数组、剑指 Offer II 010. 和为 k 的子数组 等共同构成"前缀和 + 二分/哈希"的完整学习路径。
五、同型延伸:从"最短合法区间"到"最长合法区间"
本题是"和 ≥ target 的最短子数组",其镜像问题是"成本 ≤ 预算的最长子数组"。1208. 尽可能使字符串相等(中等).md 正是这样一道题:预处理出逐字符修改成本的前缀和 sum 后,任意区间 [i, j] 的总成本可由 sum[j] - sum[i-1] O(1) 得出,随后问题变成"找成本不超过 maxCost 的最大窗口长度"。
值得关注的是,1208 题给出了一条非常典型的三段式思考路径:
- 朴素枚举不可行:枚举窗口长度 O(n) × 扫描前缀和 O(n) = O(n²),在
n = 10^5下必然超时; - 优化方向选择:无法避免"扫描前缀和判断合法性",因此只能"减少需要枚举的窗口长度",一个 O(n) 的下界优化方向自然是二分 → O(log n);
- 二分合理性论证:若答案长度为
ans,则所有≤ ans的窗口长度成本必然≤ maxCost,所有> ans的窗口长度成本必然> maxCost——ans在数轴[1, n]上具有二段性,二分成立。该文档还特别强调了一个易错认知:"二分的本质是二段性,而非单调性"。
这道题可以与 209 题互为镜像对照:209 在"固定右端点"后用二分找左边界,1208 在"二分窗口长度"后用 check 函数线性扫描;前者体现"端点枚举 + 内部二分",后者体现"长度二分 + 整体扫描"。把两道题放在一起刷,可以一次性打通「前缀和 + 二分」这一组合套路的全部变体。
此外,仓库中 剑指 Offer II 008. 和大于等于 target 的最短子数组(中等).md 与本题完全同题(仅题库不同),可直接互相印证;剑指 Offer II 009. 乘积小于 K 的子数组(中等).md 则把"窗口和"替换为"窗口乘积",进一步考验滑动窗口模板的迁移能力。
六、小结
- 长度最小的子数组是一道把两个高频套路融合在同一道题中的经典中等题:
- 前缀和 + 二分:利用正数保证的单调递增性,固定右端点后在
[0, i]内二分"≤ sum[i] - target 的最大下标",得到 O(n log n) 解法,空间 O(n); - 滑动窗口:利用全正数保证的窗口和单调性,固定右端点后贪心收缩左端点,得到 O(n) 解法,空间 O(1)。
解题时建议按以下顺序组织思考:
- 先看约束:
n <= 10^5排除 O(n²);nums[i] >= 1决定"单调性"这一核心武器; - 优先写出滑动窗口解法(代码最短、复杂度最优),可作为面试首选;
- 再补出前缀和 + 二分解法(体现对二段性的理解),两种写法均已在上述四种语言中给出可直接提交的完整实现;
- 若题目把"和 ≥ target"改为"成本 ≤ 预算"等镜像条件,参照 1208. 尽可能使字符串相等 的"长度二分 + check 扫描"模式即可完成迁移。
全套题解与代码均收录于本仓库,读者可自行在本地阅读、调试与提交。