LeetCode LCR 008. 长度最小的子数组
目录
题目描述
题意分析
给一个含 $n$ 个正整数的数组
nums和一个正整数target，找出其中和大于等于target的最短连续子数组，返回它的长度；如果不存在这样的子数组，返回 $0$。「连续子数组」这四个字把候选解限制成了 $O(n^2)$ 个区间，而不是 $2^n$ 个子序列。要求的是长度最小值，说明我们只关心区间的两个端点，不关心里面具体是哪些数。
最关键的约束是所有元素都是正整数。它带来一条极强的性质：区间和关于区间的包含关系是严格单调的——区间往右扩，和只增不减；往左收，和只减不增。没有这条性质（比如允许负数），下面所有的收缩推理都会失效。这条约束就是本题的算法信号。
数据规模是 $n \le 10^5$，$O(n^2)$ 的枚举约 $10^{10}$ 次，必然超时；$O(n \log n)$ 和 $O(n)$ 都能过。题目通常还会附加进阶要求：如果你已经实现了 $O(n)$ 的解法，请尝试 $O(n \log n)$ 的版本——反过来说，$O(n)$ 才是这道题真正的目标。
边界方面：整个数组的和可能都小于
target，此时必须返回 $0$ 而不是某个哨兵值；也可能单个元素就大于等于target，此时答案是 $1$。这两种情况都应由「答案变量的初值 + 结尾的一次转换」自然覆盖。
解法：二分查找判定答案
核心思路
暴力做法是枚举左端点，再向右累加直到和达标，$O(n^2)$。瓶颈在于：当左端点从
i移到i + 1时，右端点被无脑重置回了i + 1，前一轮已经算过的和整个作废。观察点是元素全为正带来的单调性：设
f(i)表示以i为左端点、使区间和首次达标的最小右端点。当左端点右移一格时，区间和只会变小，因此为了重新达标，右端点绝不可能左移，即f(i)关于i单调不减。既然两个端点都只向右走、各自最多走 $n$ 步，就可以用一个同向移动的窗口把总代价压到 $O(n)$。于是状态设计为：
[i, j]是当前窗口，s恒等于nums[i..j]的和。外层让j逐格右移并把nums[j]计入s（扩张）；内层在s >= target时不断把nums[i]移出并右移i（收缩）。要维持的不变量是：每次内层循环开始时，[i, j]是以j为右端点的、仍然达标的窗口中最短的那一批候选之一；内层退出后，[i, j]是以j为右端点的所有达标窗口中最短的那个再收缩一步的结果（即已不再达标）。所以答案必须在收缩之前、s >= target仍成立时更新。这样每个
j都在退出内层前贡献过它的最优答案，而每个下标至多被j访问一次、被i访问一次，总共 $O(n)$。另一条思路是前缀和 + 二分：由于元素全正，前缀和数组严格递增，对每个右端点
j二分找最大的i使pre[j] - pre[i] >= target，总代价 $O(n \log n)$。它正是题目进阶里提到的那个版本，思路同样依赖「全为正数」这一条件，只是把「同向双指针」换成了「在单调数组上折半」。窗口版更短、更快，也更适合白板手写，所以下面的实现选它。无解的处理靠初值：
answer初始化为一个大于任何合法长度的哨兵（这里用1 << 30），若循环结束它没被更新过，说明整个数组的和都不够，返回 $0$。
解题步骤
- 初始化
answer为哨兵大值、s = 0、i = 0。哨兵必须大于任何可能的长度 $n$，用1 << 30而不是Integer.MAX_VALUE是为了后续若有加法也不会溢出。- 外层
j从 $0$ 扫到 $n-1$，先执行s += nums[j]。先扩张再判断，保证进入内层时s与窗口[i, j]严格对应。- 内层用
while (s >= target)而不是if。一次扩张后可能需要连续收缩多格（比如刚加入的元素本身就远大于target），if只收一格会漏掉更短的答案。- 在收缩之前更新答案：
answer = min(answer, j - i + 1)。此刻s >= target成立，[i, j]是合法窗口；一旦执行了s -= nums[i]，窗口就可能不再达标，那时再取长度就是错的。- 收缩时同步减和与移指针：
s -= nums[i++]。两者必须成对出现，否则s与窗口的对应关系（不变量）立刻被破坏。- 内层的收缩条件不需要额外的
i <= j保护。因为元素全为正且target为正，s在窗口收缩到空时必然变成 $0$，$0 < target$ 会自动终止循环。- 结尾把哨兵转成 $0$：
return answer == inf ? 0 : answer;。这是题目对无解情形的约定。以
target = 7、nums = [2, 3, 1, 2, 4, 3]走一遍，期望答案2。初始i = 0, s = 0, answer = inf。j = 0：s = 2，不达标。j = 1：s = 5，不达标。j = 2：s = 6，不达标。j = 3：s = 8 >= 7，更新answer = 3 - 0 + 1 = 4，收缩掉nums[0] = 2，s = 6、i = 1，不再达标。j = 4：s = 10 >= 7，更新answer = min(4, 4 - 1 + 1) = 4，收缩掉nums[1] = 3，s = 7、i = 2；仍>= 7，更新answer = min(4, 4 - 2 + 1) = 3，收缩掉nums[2] = 1，s = 6、i = 3，退出。j = 5：s = 9 >= 7，更新answer = min(3, 5 - 3 + 1) = 3，收缩掉nums[3] = 2，s = 7、i = 4；仍>= 7，更新answer = min(3, 5 - 4 + 1) = 2，收缩掉nums[4] = 4，s = 3、i = 5，退出。循环结束，answer = 2，对应子数组[4, 3]。注意j = 4和j = 5都发生了连续两次收缩——这正是内层必须写while的直接证据。
代码实现
class Solution {
public int minSubArrayLen(int target, int[] nums) {
final int inf = 1 << 30;
int answer = inf;
int s = 0;
for (int i = 0, j = 0; j < nums.length; ++j) {
s += nums[j];
// 元素全为正，达标后继续收缩仍可能达标，必须用 while。
while (s >= target) {
// 先在窗口仍合法时更新答案，再收缩。
answer = Math.min(answer, j - i + 1);
s -= nums[i++];
}
}
return answer == inf ? 0 : answer;
}
}
func minSubArrayLen(target int, nums []int) int {
const inf = 1 << 30
answer := inf
s, i := 0, 0
for j, x := range nums {
s += x
for s >= target {
answer = min(answer, j-i+1)
s -= nums[i]
i++
}
}
if answer == inf {
return 0
}
return answer
}
复杂度分析
- 时间复杂度：$O(n)$。左右两个下标都只向右移动、各自至多走 $n$ 步，所以内层
while的总执行次数被i的总位移量摊还成 $O(n)$，而不是每轮各跑一遍。凭的是元素全正带来的单调性，它保证了i永远不需要回退。- 空间复杂度：$O(1)$。只用了
answer、s、i、j四个标量，没有前缀和数组也没有任何容器。
关键点总结
- 「连续子数组 + 全为正数 + 求最短/最长」是滑动窗口最典型的触发组合；一旦允许负数，区间和的单调性消失，就必须换成前缀和加单调队列（对应 862 题）。
- 滑动窗口的正确性论证要落在「左端点单调不回退」上：证明了左端点不需要回退，才有 $O(n)$ 的摊还复杂度。
- 答案的更新时机由窗口的合法性决定：求「最短且满足条件」时在收缩前更新（此刻合法），求「最长且满足条件」时在收缩后更新（收缩后才恢复合法）。这一条是区分两类窗口题的分水岭。
- 循环变量
s必须与窗口范围保持严格对应，任何一次指针移动都要配一次和的增减，把它当作不变量来维护。- 用「哨兵初值 + 结尾转换」代替「先判断是否有解」的前置特判，能让主逻辑保持单一出口。
- 面试视角：面试官期待的主解法就是这份 $O(n)$ 窗口。写完后主动补一句「因为元素全为正，左端点单调不减，所以是 $O(n)$ 而不是 $O(n^2)$」是关键得分点；若被追问进阶的 $O(n \log n)$，就给出前缀和 + 二分的版本，并说明它的价值在于「当题目改成求恰好等于某值或数据需要离线处理时更容易推广」。
易错点总结
- 错误写法：内层用
if (s >= target)而不是while。输入target = 7, nums = [2, 3, 1, 2, 4, 3]时j = 5只收缩一格就退出，答案停在3，正确值是2。- 错误写法：先
s -= nums[i++]再更新答案。输入target = 4, nums = [1, 4, 4]时，j = 1处收缩后窗口已变成空，长度算成1 - 1 + 1 = 1看似碰巧对，但target = 11, nums = [1, 2, 3, 4, 5]会算出比真实值更小的长度，返回2而不是3。- 错误写法：
answer初始化为 $0$。Math.min(0, ...)恒为 $0$，任何输入都返回0。- 错误写法：
answer初始化为Integer.MAX_VALUE且结尾忘记转 $0$。输入target = 11, nums = [1, 1, 1]会返回2147483647而不是0。- 错误写法：收缩时只写
s -= nums[i]忘记++i。i永远停在 $0$，窗口长度再也不会变短，输入target = 7, nums = [2, 3, 1, 2, 4, 3]会返回4而不是2。- 错误写法：把窗口长度算成
j - i。少算一格，输入target = 4, nums = [4]会返回0（长度算成 $0$，又恰好等于「无解」的返回值），正确答案是1。- 错误写法：内层条件写成
s > target。输入target = 4, nums = [4]时s == target不进内层，返回0而不是1；题目要的是「大于等于」。- 错误写法：把这套窗口直接用在含负数的变体上。输入
target = 3, nums = [1, -1, 3]会返回3，而正确答案是1（子数组[3]）：负数让区间和不再随扩张单调递增，收缩到s < target就停下的判据彻底失效——这类题必须改用前缀和加单调队列。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 209. 长度最小的子数组 | 中等 | 与本题同题，可直接套用同一份窗口 |
| 713. 乘积小于 K 的子数组 | 中等 | 求方案数而非长度，命中时一次性加上 j - i + 1 个子数组 |
| LCR 009. 乘积小于 K 的子数组 | 中等 | 与 713 同题，把和换成积，收缩条件与溢出处理是新增难点 |
| 1658. 将 x 减到 0 的最小操作数 | 中等 | 需先把「删两端最少」反转成「留中间最长且和为定值」再滑窗 |
| 3. 无重复字符的最长子串 | 中等 | 求最长，答案要在收缩完成、窗口恢复合法之后更新 |
| 424. 替换后的最长重复字符 | 中等 | 窗口合法性依赖「窗口长度减最高频字符数」，需额外维护频次最大值 |
| 1004. 最大连续1的个数 III | 中等 | 收缩依据换成窗口内 $0$ 的个数是否超过 k
|
| 862. 和至少为 K 的最短子数组 | 困难 | 允许负数，单调性失效，必须改用前缀和 + 单调队列 |