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

滑动窗口（同向区间指针）

滑动窗口是数组 / 字符串类题目里出镜率极高的套路。掌握它，能让一大批看似 O(n²) 的暴力解法瞬间降到 O(n)。本文从"定长"和"变长"两个视角，配合可直接套用的模板代码，帮你一次性理清思路。

一、什么是滑动窗口？

滑动窗口（Sliding Window）属于双指针中的一种——同向指针。两个指针left和right同时从数组左端出发，向右移动，圈出一个不断变化的"窗口"。

它的核心思想是：在窗口滑动的过程中，利用已经计算好的信息，避免重复计算。

根据窗口大小是否固定，可以分为两类：

二、定长滑动窗口（固定相框）📷

想象你拿着一个尺寸固定的相框，在数组上从左往右一格一格地平移。每移动一次，画面里就进来一个新元素，挤出去一个老元素。

套路三步走

1. 初始化：先计算前k个元素构成的第一个窗口的状态（和、计数、最大值等）。
2. 滑动：窗口整体向右平移，每次加一个新进来的nums[i]，减一个被踢出去的nums[i-k]。
3. 更新答案：在每次滑动后记录当前窗口的结果。

全程只需一层循环，时间复杂度 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：子数组最大平均数 I
• 🔹LeetCode 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：找到字符串中所有字母异位词

四、使用滑动窗口的信号 🚦

当题目同时满足以下特征时，优先考虑滑动窗口：

• 处理连续的子数组 / 子串 / 子序列。
• 求满足某条件的最长 / 最短 / 定长区间。
• 数据具有单调性：窗口扩大时某个指标单调变化（如和变大、字符种类变多）。

⚠️注意：如果数组中包含负数，窗口和就不再单调，此时滑动窗口可能失效，需要考虑前缀和 + 哈希表等其它思路。