滑动窗口算法：双指针高效解题秘籍

一、上期回顾

掌握单调栈核心逻辑，快速查找左右侧最值元素，搞定每日温度、下一个更大元素等经典题。今天学习滑动窗口，双指针经典算法，解决子数组、子串、区间求和类高频考题。

二、滑动窗口核心概念

滑动窗口 =左右双指针划定一个连续区间

• 左指针 left：窗口左边界
• 右指针 right：窗口右边界
• 窗口不断向右滑动，动态收缩左边界，满足题意
• 时间复杂度：O(n)，远优于暴力双重循环 O (n²)

两大分类

1. 固定长度窗口：窗口大小固定，依次滑动统计
2. 可变长度窗口：窗口大小不固定，求最长 / 最短合法区间

三、固定长度滑动窗口（模板）

适用：定长子数组求和、平均值、最大最小值

#include <iostream> #include <vector> #include <algorithm> using namespace std; // 求长度为k的子数组最大和 int maxSumFixedWindow(vector<int>& nums, int k) { int sum = 0; // 初始化第一个窗口 for(int i = 0; i < k; i++) sum += nums[i]; int max_val = sum; // 滑动窗口 for(int i = k; i < nums.size(); i++) { sum = sum - nums[i - k] + nums[i]; max_val = max(max_val, sum); } return max_val; } int main() { vector<int> arr = {1,3,-1,2,5}; cout << maxSumFixedWindow(arr,3); return 0; }

四、可变长度滑动窗口（通用核心模板）

通用思路

1. 右指针不断右移扩大窗口
2. 窗口不满足条件时，左指针右移缩小窗口
3. 过程中记录最优答案

模板框架

int left = 0; for(int right = 0; right < n; right++) { // 1. 加入右边界元素，更新窗口状态 // 2. 窗口不合法，收缩左边界 while(窗口不满足条件) { // 移除左边界元素 left++; } // 3. 记录最优答案 }

五、经典例题 1：最长无重复子串

int lengthOfLongestSubstring(string s) { int cnt[128] = {0}; int left = 0, res = 0; for(int right = 0; right < s.size(); right++) { char c = s[right]; cnt[c]++; // 出现重复字符，收缩左边界 while(cnt[c] > 1) { cnt[s[left]]--; left++; } res = max(res, right - left + 1); } return res; }

六、经典例题 2：最小子数组和大于目标值

int minSubArrayLen(int target, vector<int>& nums) { int left = 0, sum = 0; int res = 1e9; for(int right = 0; right < nums.size(); right++) { sum += nums[right]; // 满足条件就尽量缩小窗口 while(sum >= target) { res = min(res, right - left + 1); sum -= nums[left]; left++; } } return res == 1e9 ? 0 : res; }

七、滑动窗口使用禁忌

滑动窗口只适用于：区间具有单调性满足：窗口扩张条件变松，窗口收缩条件变紧不适用：元素正负杂乱、无单调规律题型

八、今日核心总结

1. 滑动窗口依靠左右双指针，线性遍历高效解题
2. 分定长窗口与变长窗口两类题型
3. 右扩左缩，先扩后缩，动态维护合法区间
4. 字符串子串、数组子数组、区间统计优先用滑动窗口
5. 核心口诀：右指针无脑走，不合法左指针缩

九、课后练习

1. 用固定窗口求数组内长度为 2 的最小和
2. 手写最长无重复子串滑动窗口代码
3. 自行实现最短子数组满足和大于给定值