滑动窗口算法简介
滑动窗口是一种用于处理数组或字符串子区间问题的高效算法。它通过维护一个动态窗口（通常由两个指针表示）来避免重复计算，将时间复杂度从O(n²)优化到O(n)。
基本实现步骤
- 初始化窗口指针：通常使用
left和right指针表示窗口的左右边界。 - 移动右指针：逐步扩展窗口，直到满足特定条件（如窗口内元素和达到目标值）。
- 调整左指针：当条件满足时，收缩窗口以寻找更优解或继续下一轮搜索。
示例代码
以下是一个求“和大于等于目标值的最短子数组长度”的滑动窗口实现：
public int minSubArrayLen(int target, int[] nums) {int left = 0, sum = 0;int minLength = Integer.MAX_VALUE;for (int right = 0; right < nums.length; right++) {sum += nums[right];while (sum >= target) {minLength = Math.min(minLength, right - left + 1);sum -= nums[left++]; // 收缩窗口}}return minLength == Integer.MAX_VALUE ? 0 : minLength;
}
常见应用场景
- 固定窗口大小：如计算大小为k的子数组的平均值。
- 可变窗口大小：如寻找满足条件的最短/最长子数组。
- 字符串匹配：如找到包含所有目标字符的最小窗口。
注意事项
- 边界条件：处理空数组或无法满足条件的情况。
- 负数处理：若数组包含负数，滑动窗口可能失效，需改用其他方法（如前缀和+哈希表）。
- 复杂度分析：确保每个元素最多被访问两次（O(n)时间复杂度）。
变式问题
- 无重复字符的最长子串（LeetCode 3）：使用哈希表记录字符最后出现位置。
- 最大连续1的个数 III（LeetCode 1004）：通过计数允许的翻转次数来维护窗口。
