算法:滑动窗口技巧与应用
1. 长度最小的子数组

解题原理

📋 解题步骤
第一步:理解题意
- 找一个连续子数组,使其和 ≥ target,且长度最小
- 数组元素都是正整数(关键性质)
- 无解返回 0
第二步:分析暴力解法
- 枚举所有子数组:O(n²) 或 O(n³)
- 对于 n = 10⁵ 会超时
第三步:寻找优化点
- 正整数 → 窗口扩展时和单调递增
- 可以用滑动窗口优化
第四步:设计滑动窗口
遍历右指针:扩展窗口,从右边进窗口
判断:如果 sum >= target:更新最小长度,收缩窗口,从左边出窗口
第五步:手动模拟
| 步骤 | left | right | 窗口 | sum | result |
|---|
| 4 | 0 | 3 | [2,3,1,2] | 8 | 4 |
| 7 | 2 | 4 | [1,2,4] | 7 | 3 |
| 10 | 4 | 5 | [4,3] | 7 | 2 |
第六步:编写代码
class Solution {
public:
int minSubArrayLen(int target, vector<>& nums) {
len = INT_MAX;
n = nums.();
sum = ;
( left = , right = ; right < n; right++) {
sum += nums[right];
(sum >= target) {
len = (len, right - left + );
sum -= nums[left++];
}
}
len == INT_MAX ? : len;
}
};