一.什么是滑动窗口
想象一下，你正在透过一个固定大小的窗口观察一条长长的数据序列，这个窗口可以左右滑动，让你看到序列的不同部分——这就是滑动窗口算法的直观理解。
滑动窗口是一种用于处理数组/字符串子区间问题的优化技巧。它通过维护一个窗口（通常是连续的子数组或子字符串），在遍历过程中动态地调整窗口的左右边界，从而高效地解决问题。
二.为什么需要滑动窗口
让我们先来看一个经典问题：
给定一个字符串，找出其中不含有重复字符的最长子串的长度。
暴力解法：枚举所有子串，检查是否重复
// 时间复杂度：O(n³) 或 O(n²)
bool hasDuplicate(string s, int start, int end) {unordered_set seen;for (int i = start; i <= end; i++) {if (seen.count(s[i])) return true;seen.insert(s[i]);}return false;
}
int bruteForce(string s) {int maxLen = 0;for (int i = 0; i < s.length(); i++) {for (int j = i; j < s.length(); j++) {if (!hasDuplicate(s, i, j)) {maxLen = max(maxLen, j - i + 1);}}}return maxLen;
} 这种解法在长字符串面前会变得极其缓慢。而滑动窗口算法可以在O(n)时间内解决这个问题
三.核心思想
滑动窗口通过维护一个窗口（连续的子数组/子字符串），在遍历过程中动态调整窗口的左右边界，避免重复计算。
窗口中可以直接访问到的值一般就是目标值,将嵌套多层for循环问题转化为单次遍历，将时间复杂度从 O(n²) 降低到 O(n)。
四.使用场景
(1)关于连续子数组/子字符串的
(2)要求找到满足某些条件的最长/最短子区间
(3)统计满足条件的子区间个数
五.滑动窗口的类型
滑动窗口也分为两种类型,一种是窗口定长的,还有一种是窗口长度可变的
(1)定长窗口
例题:大小为k的子数组的最大平均值
double findMaxAverage(vector& nums, int k) {double windowSum = 0;// 初始化第一个窗口for (int i = 0; i < k; i++) {windowSum += nums[i];}double maxSum = windowSum;// 滑动窗口for (int i = k; i < nums.size(); i++) {//每次移动时将左边界元素减去,将右边界元素加上windowSum += nums[i] - nums[i - k];//判断最大值maxSum = max(maxSum, windowSum);}return maxSum / k;
} (2)不定长窗口:
不定长窗口相对定长窗口来说更加灵活,可以动态的变化窗口大小,满足多种情况,但是也更需要判断何时收缩,可能因为一个小小的误判,就会导致整个窗口中的元素变为无效
力扣209:长度最小的子数组
给定一个含有 n个正整数的数组和一个正整数 target 。
找出该数组中满足其总和大于等于target的长度最小的 子数组[numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。
示例 1：
[4,3]示例 2：
输入：target = 4, nums = [1,4,4]
输出：1示例 3：
输入：target = 11, nums = [1,1,1,1,1,1,1,1]
输出：0思路:
动态维护一个滑动窗口,当窗口内元素和小于target时,移动右边界,扩大窗口,当窗口内元素和大于等于target时,就尝试收缩左边界,直到元素和再次小于target,重复这个过程,直到遍历完整个数组
class Solution {
public:int minSubArrayLen(int target, vector& nums) {int l = 0,sums = 0;//初始化左边界以及元素和int minl = INT_MAX;//记录最小子数组长度for(int i = 0;i=target){minl = min(minl,i-l+1);//更新最小长度sums -= nums[l];//将收缩后移出子数组的元素减去l++;//左边界收缩}}//判断有没有找到最小子数组if(minl == INT_MAX){return 0;}else{return minl;}}
}; 六.滑动窗口的综合使用
滑动窗口也可以和其他数据结构一起使用,以解决更多的类型的题目
(1)滑动窗口+哈希表
力扣3:无重复字符的最长子串
给定一个字符串 s ，请你找出其中不含有重复字符的 最长 子串的长度。
示例 1:
"abc"示例 2:
"b"示例 3:
"wke"思路:
用一个哈希表去记录滑动窗口中的数字,每遍历到一个新的数字时,若其在哈希表中说明重复,反之则不重复,这也是处理重复数据问题最常用的方法.
class Solution {
public:int lengthOfLongestSubstring(string s) {//哈希表unordered_mapmp;int left = 0;//左边界int maxLen = 0;//最大长度//遍历数组for(int i = 0;i=left){//将左边界直接更新到该元素最后出现位置的后一位,避免多次多余判断left = mp[s[i]]+1;}//将数据加入哈希表中mp[s[i]]=i;maxLen = max(maxLen,(i-left+1));//更新最大长度}return maxLen;}
}; 力扣904:水果成篮
你正在探访一家农场，农场从左到右种植了一排果树。这些树用一个整数数组 fruits 表示，其中 fruits[i] 是第 i 棵树上的水果 种类 。
你想要尽可能多地收集水果。然而，农场的主人设定了一些严格的规矩，你必须按照要求采摘水果：
- 你只有 两个 篮子，并且每个篮子只能装 单一类型 的水果。每个篮子能够装的水果总量没有限制。
- 你可以选择任意一棵树开始采摘，你必须从 每棵 树（包括开始采摘的树）上 恰好摘一个水果 。采摘的水果应当符合篮子中的水果类型。每采摘一次，你将会向右移动到下一棵树，并继续采摘。
- 一旦你走到某棵树前，但水果不符合篮子的水果类型，那么就必须停止采摘。
给你一个整数数组 fruits ，返回你可以收集的水果的 最大 数目。
示例 1：
输入：fruits = [1,2,1]
输出：3
解释：可以采摘全部 3 棵树。示例 2：
输入：fruits = [0,1,2,2]
输出：3
解释：可以采摘 [1,2,2] 这三棵树。
如果从第一棵树开始采摘，则只能采摘 [0,1] 这两棵树。示例 3：
输入：fruits = [1,2,3,2,2]
输出：4
解释：可以采摘 [2,3,2,2] 这四棵树。
如果从第一棵树开始采摘，则只能采摘 [1,2] 这两棵树。示例 4：
输入：fruits = [3,3,3,1,2,1,1,2,3,3,4]
输出：5
解释：可以采摘 [1,2,1,1,2] 这五棵树。思路:
使用一个哈希表去存储篮子中已有的水果种类,当大于2时,持续收缩左边界,直到种类重新小于2
class Solution {
public:int totalFruit(vector& fruits) {//初始化unordered_mapmp;int maxNum = 0;int left = 0;//遍历数组for(int i = 0;i2){//收缩左边界,将移出的种类的水果数量-1mp[fruits[left]]--;//更新左边界left++;//当某种水果数量为0时,删除这种种类if(mp[fruits[left]]==0){mp.erase(fruits[left]);}}//记录满足要求的窗口的长度maxNum = max(maxNum,(i-left+1));}return maxNum;}
}; (2)滑动窗口+特殊队列
力扣239:滑动窗口最大值
给你一个整数数组 nums，有一个大小为 k的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回 滑动窗口中的最大值 。
示例 1：
输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]
解释：滑动窗口的位置 最大值
--------------- ----
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7
思路:
通过维护一个单调双端队列(deque)来达到快速找到最大值的目的
先遍历前k个元素,用一个单调队列找到最大值,并将最大值存入结果数组中.
再从第k个元素开始遍历,每次遍历都将该数存入队列中,并维护队列的单调性,确保队列中的头部元素即为该窗口的最大值
通过一个left变量控制滑动窗口的左边界,每次循环将其+1,如果发现左边界的值就是队列头部元素的值,说明最大值要被移出窗口了,就把队列头部元素删除
由于我们维护的是单调队列,在没有更大的元素进入窗口时,删去头部元素后,新的头部元素仍然是窗口的最大值
class Solution {
public:vector maxSlidingWindow(vector& nums, int k) {if(nums.size()<=1){return nums;}dequeque;//双端队列,可以删除头部也可以删除尾部que.push_back(nums[0]);vectorvec;//结果数组//遍历前k个元素并维护单调队列for(int i = 1;ique.back()){que.pop_back();}que.push_back(nums[i]);//双端队列的插入}//将第一个滑动窗口的最大值存入结果数组中vec.push_back(que.front());//记录左边界int left = 0;//从第k个元素开始遍历for(int i = k;ique.back()){que.pop_back();}que.push_back(nums[i]);//判断最大值会不会随着左边界收缩而被移出窗口,如果会就把最大值从队列中删除if(nums[left]==que.front()){que.pop_front();}left++;//左边界收缩vec.push_back(que.front());//将最大值存入结果数组}return vec;}
}; 七.总结
滑动窗口算法之所以强大，在于它：
高效：将O(n²)优化到O(n)
直观：符合人类的思维习惯
通用：有固定的模板可以套用
灵活：适用于各种变种问题
希望这篇指南能帮助你掌握这个强大的算法技巧!加油!!!