双指针与滑动窗口中等2 种解法
#209长度最小的子数组
在正整数数组中寻找元素和至少为 target 的最短连续子数组，不存在时返回 0。
#数组#滑动窗口#前缀和
原题
给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其总和大于等于 target 的长度最小的 子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 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 <= 1091 <= nums.length <= 1051 <= nums[i] <= 104
进阶：
- 如果你已经实现
O(n)时间复杂度的解法, 请尝试设计一个O(n log(n))时间复杂度的解法。
解题主线
- 所有元素均为正数，因此右端加入元素只会让窗口和增大，左端移出元素只会让窗口和减小。
- 窗口达到 target 后应持续收缩并记录长度，直到再次不满足条件，才能保证不会遗漏更短答案。
- 双重枚举在固定起点后可一边扩展终点一边累加，命中后立即停止该起点的扫描。
解法 1：枚举起点与终点
固定每个起点，向右累加到首次达到 target；因为元素为正，之后只会更长，可以立刻处理下一个起点。
-
时间复杂度： O(n²)
-
空间复杂度： O(1)
final class Solution {
public int minSubArrayLen(int target, int[] nums) {
// Integer.MAX_VALUE 作为“尚未找到可行区间”的哨兵，返回前再转换为 0。
int minimumLength = Integer.MAX_VALUE;
// 正数保证固定左端点后区间和单调增加，首次达标即是该起点的最短区间。
for (int left = 0; left < nums.length; left++) {
int sum = 0;
for (int right = left; right < nums.length; right++) {
sum += nums[right];
if (sum >= target) {
minimumLength = Math.min(minimumLength, right - left + 1);
break;
}
}
}
return minimumLength == Integer.MAX_VALUE ? 0 : minimumLength;
}
}解法 2：同向双指针滑动窗口
右指针逐项扩张并累加；窗口和达标时反复移动左指针，在失去可行性前更新最短长度。
-
时间复杂度： O(n)，每个元素最多进入和离开窗口各一次
-
空间复杂度： O(1)
final class Solution {
public int minSubArrayLen(int target, int[] nums) {
int left = 0;
int sum = 0;
int minimumLength = Integer.MAX_VALUE;
// 窗口 [left, right] 的 sum 与指针移动保持同步，每个元素最多进出一次。
for (int right = 0; right < nums.length; right++) {
sum += nums[right];
// 元素均为正；达标后持续右移 left，才能得到该右端点下的最短可行窗口。
while (sum >= target) {
minimumLength = Math.min(minimumLength, right - left + 1);
sum -= nums[left++];
}
}
return minimumLength == Integer.MAX_VALUE ? 0 : minimumLength;
}
}边界与易错点
- 滑动窗口解法依赖 nums 中都是正整数；若允许负数，窗口和不再具备单调性。
- 无解时不能返回 Integer.MAX_VALUE，应转换为 0。
- 连续子数组不能跳过中间元素。
整理来源
由旧仓库源码复核、去重并整理；展示代码已按 Java 21 语义修正明显问题。
leetcode/src/main/java/medium/Q209_minSubArrayLen.java