1. 长度最小的子数组
给定一个含有 n 个正整数的数组和一个正整数 target。
找出该数组中满足其总和大于等于 target 的长度最小的子数组，并返回其长度。如果不存在符合条件的子数组，返回 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.1 题目解析
针对一段连续区间，寻找最小长度的子数组，使其元素和大于等于给定目标值（通常称为'最小子数组和'问题），利用正数相加和只能增加的单调性，使用滑动窗口方法解决。此利用单调性避免没有必要的枚举行为。虽然有两层循环，但是时间复杂度为 O(N)。
1.2 解法
滑动窗口的核心是使用两个指针（左指针和右指针）动态调整窗口范围：
- 窗口定义：窗口代表子数组，其和记为 sum。
- 目标：找到最小长度 minLen。
- 关键思想：
- 移动 right 扩大窗口，增加 sum，直到 sum >= target。
- 然后移动 left 缩小窗口，减少 sum，同时检查是否仍满足 sum >= target (因为移除小元素可能保留满足条件的更小子数组)。
- 更新 minLen 为当前窗口长度 right-left+1 的最小值。
- 为什么高效：每个元素最多被添加和移除一次，确保线性时间复杂度。
以下是滑动窗口算法的具体步骤：
- 初始化指针：左右指针定义从 0 下标开始。
- 移动右指针：将 right 位置的元素加入窗口，直到 sum >= target。
- 缩小窗口并检查：将 left 位置的元素移动出窗口，并且检查是否 sum >= target。
- 循环步骤 2、3 直到 right >= n。
1.3 代码实现
class Solution {
public int minSubArrayLen(int target, int[] nums) {
int minLen = Integer.MAX_VALUE;
int n = nums.length;
int sum = ;
( , right = ; right < n; right++) {
sum += nums[right];
(sum >= target) {
right - left + ;
minLen = Math.min(minLen, length);
sum -= nums[left++];
}
}
minLen == Integer.MAX_VALUE ? : minLen;
}
}
