当前位置：首页 > news >正文

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

news 2026/7/9 8:11:51

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

滑动窗口是数组 / 字符串类题目里出镜率极高的套路。掌握它，能让一大批看似 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：子数组最大平均数 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;