简要介绍
滑动窗口是处理数组和字符串问题的常用技巧,尤其在寻找满足特定条件的子数组或子串时非常高效。它的核心思想是维护一个动态区间(即'窗口'),通过移动左右边界来扫描数据结构。
基本套路通常包含四个步骤:
- 扩张:右指针移动,将元素纳入窗口。
- 判断:检查当前窗口是否满足条件。
- 收缩:若满足条件,尝试移动左指针缩小窗口以优化结果。
- 更新:记录过程中的最优解。
下面我们通过四道经典例题来深入理解这一算法。
长度最小的子数组
题目描述
给定一个含有 n 个正整数的数组和一个正整数 target。找出该数组中满足其总和大于等于 target 的长度最小子数组,并返回其长度。如果不存在符合条件的子数组,返回 0。
示例:
- 输入:
target = 7,nums = [2,3,1,2,4,3] - 输出:
2 - 解释:子数组
[4,3]是该条件下的长度最小子数组。
提示:
1 <= target <= 10^91 <= nums.length <= 10^5
实现思路
暴力解法需要遍历所有子数组,时间复杂度为 O(n²),在数据量较大时会超时。我们可以利用滑动窗口将复杂度优化至 O(n)。
具体做法是维护一个累加和 sum。右指针不断向右扩展,将数值加入 sum;一旦 sum >= target,说明当前窗口满足条件,此时尝试移动左指针缩小窗口,同时更新最小长度。这样每个元素最多被访问两次。
代码实现
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int n = nums.size(), sum = 0, len = INT_MAX;
for (int left = 0, right = 0; right < n; right++) {
sum += nums[right]; // 进窗口
while (sum >= target) {
len = min(len, right - left + 1); // 更新结果
sum -= nums[left++];
}
}
len == INT_MAX ? : len;
}
};


