【算法复习】滑动窗口（同向区间指针）

滑动窗口同向区间指针滑动窗口是数组 / 字符串类题目里出镜率极高的套路。掌握它能让一大批看似 O(n²) 的暴力解法瞬间降到 O(n)。本文从定长和变长两个视角配合可直接套用的模板代码帮你一次性理清思路。一、什么是滑动窗口滑动窗口Sliding Window属于双指针中的一种——同向指针。两个指针left和right同时从数组左端出发向右移动圈出一个不断变化的窗口。它的核心思想是在窗口滑动的过程中利用已经计算好的信息避免重复计算。根据窗口大小是否固定可以分为两类类型窗口大小典型问法定长滑动窗口固定为k“长度为 k 的子数组/子串中……的最大/最小值”变长滑动窗口动态变化“满足 XX 条件的最长/最短子数组”二、定长滑动窗口固定相框想象你拿着一个尺寸固定的相框在数组上从左往右一格一格地平移。每移动一次画面里就进来一个新元素挤出去一个老元素。套路三步走初始化先计算前k个元素构成的第一个窗口的状态和、计数、最大值等。滑动窗口整体向右平移每次加一个新进来的nums[i]减一个被踢出去的nums[i-k]。更新答案在每次滑动后记录当前窗口的结果。全程只需一层循环时间复杂度 O(n)。模板代码// 1. 初始化第一个长度为 k 的窗口 let sum 0; for (let i 0; i k; i) { sum nums[i]; // 累加状态 } let res sum; // 2. 开始滑动 for (let i k; i nums.length; i) { // 进一个 nums[i]出一个 nums[i-k] sum nums[i] - nums[i - k]; // 更新最大/最小值 res Math.max(res, sum); } return res;典型例题LeetCode 643子数组最大平均数 ILeetCode 1456定长子串中元音的最大数目LeetCode 2090半径为 k 的子数组平均值三、变长滑动窗口毛毛虫变长窗口更像一只毛毛虫头right先往前拱一拱拱到不舒服了尾巴left再跟上来缩一缩如此反复向前爬行。套路要点外层循环右指针right不断向右拉伸把新元素纳入窗口。内层循环一旦窗口满足/违反某种条件左指针left立即向右收缩直到条件恢复。关键根据题目要求的是最长还是最短决定在收缩之前还是之后更新答案。小技巧找最短→ 在 while 内部窗口刚满足条件时更新答案然后继续缩找最长→ 在 while 外部窗口刚恢复合法时更新答案。模板代码let left 0, right 0; let res 0; // 或 Infinity视题意而定 while (right nums.length) { // 【1】入窗扩展右边界 // 把 nums[right] 加入窗口更新状态 while (/* 窗口需要收缩 */) { // 【2】记录答案找「最短」时在这里更新 res // 【3】出窗收缩左边界 // 把 nums[left] 移出窗口更新状态 left; } // 【4】记录答案找「最长」时在这里更新 res right; } return res;典型例题LeetCode 209长度最小的子数组找最短LeetCode 3无重复字符的最长子串找最长LeetCode 76最小覆盖子串找最短 哈希计数LeetCode 438找到字符串中所有字母异位词四、使用滑动窗口的信号 当题目同时满足以下特征时优先考虑滑动窗口处理连续的子数组 / 子串 / 子序列。求满足某条件的最长 / 最短 / 定长区间。数据具有单调性窗口扩大时某个指标单调变化如和变大、字符种类变多。⚠️注意如果数组中包含负数窗口和就不再单调此时滑动窗口可能失效需要考虑前缀和 哈希表等其它思路。