算法：滑动窗口技巧与应用

算法：滑动窗口技巧与应用

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;
    }
};