算法从入门到精通——滑动窗口

算法从入门到精通——滑动窗口滑动窗口算法简介什么是滑动窗口滑动窗口的本质其实就是双指针即同向双指针如果让你暴力枚举所有区间时间复杂度往往是 O(n²)。但很多题目里我们其实没必要“重新遍历”整个区间。这时候滑动窗口就登场了。滑动窗口本质上是用left和right两个指针维护一个动态区间让窗口像尺子一样在数组或字符串上滑动从而在线性时间内解决问题。它最大的魅力就在于很多看似需要两层循环的问题都能被优化到 O(n)。什么时候可以使用滑动窗口判断一个题目能不能用滑动窗口关键看一个特征左右指针是否具有“单调不回退”性质。也就是说right指针不断向右扩展窗口left指针在需要时向右收缩窗口两个指针都只向前走不会后退因此每个元素最多被访问两次时间复杂度通常可以降到On接下来我们就从最经典的题型开始彻底掌握滑动窗口的核心套路。本章算法题的简单总结建议最后看1滑动窗口长度最小的子数组最大连续1的个数 III将 x 减到 0 的最小操作数2滑动窗口哈希无重复字符的最长子串水果成篮找到字符串中所有字母异位词串联所有单词的子串滑动窗口1长度最小的子数组⭐题目链接长度最小的子数组解题思路题目要求我们寻找“长度最小”的连续子数组本质上就是在数组中维护一个动态区间因此可以使用滑动窗口双指针来解决。我们用left和right两个指针维护当前窗口并记录窗口内元素之和sum。由于数组中的元素全部为正数因此窗口具有单调性当sum target时说明当前窗口不满足条件需要扩大窗口让 right 右移。当sumtarget时说明当前窗口已经满足条件此时可以尝试缩小窗口让 left 右移从而寻找更短的满足条件的子数组。在整个过程中left和right都只会向右移动一次因此时间复杂度为 O(n)。解题代码/* 解题思路 使用滑动窗口双指针维护一个连续区间[left, right]。 1. 当窗口内元素和 sum 小于 target 时 说明当前窗口不满足条件需要扩大窗口right 右移。 2. 当 sum target 时 说明当前窗口已经满足条件此时尝试缩小窗口 更新最小长度后让 left 右移寻找更短的满足条件的子数组。 由于 left 和 right 都只会向右移动一次时间复杂度为 O(n)。 */ class Solution { public: int minSubArrayLen(int target, vectorint nums) { int left 0, right 0; // 当前窗口的元素和 int sum nums[0]; // 记录最小长度 int ret 0x3f3f3f3f; // 滑动窗口 while (right nums.size() left right) { // 当前窗口和不足 target扩大窗口 if (sum target) { right; // 防止越界 if (right nums.size()) sum nums[right]; } else { // 更新最小长度 ret min(ret, right - left 1); // 缩小窗口 sum - nums[left]; left; } } // 如果没有满足条件的子数组返回 0 return ret 0x3f3f3f3f ? 0 : ret; } };没懂看看大神的解题代码大神解题代码class Solution { public: int minSubArrayLen(int target, vectorint nums) { int n nums.size(); int sum 0; // 窗口内元素和 int ret INT_MAX; // 记录最小长度初始为最大值 // 滑动窗口left为窗口左边界right为窗口右边界 for(int left 0, right 0; right n; right) { sum nums[right]; // 右指针右移元素加入窗口 // 当窗口和≥target时收缩左边界更新最小长度 while(sum target) { ret min(ret, right - left 1); // 更新当前窗口的长度 sum - nums[left]; // 移除左边界元素左指针右移 } } // 若ret仍为INT_MAX说明无有效子数组返回0否则返回ret return ret INT_MAX ? 0 : ret; } };2无重复字符的最长子串⭐⭐题目链接无重复字符的最长子串解题思路题目要求我们寻找“最长的不含重复字符的子串”本质上也是在字符串中维护一个动态区间因此可以使用滑动窗口双指针来解决。我们用left和right两个指针维护当前窗口并使用哈希表记录窗口中每个字符出现的次数。当某个字符出现重复时说明当前窗口已经不合法此时需要不断移动left缩小窗口直到窗口中不存在重复字符为止。在窗口始终合法的过程中我们不断更新窗口长度的最大值即可。由于left和right都只会向右移动一次因此时间复杂度为O(n)。解题代码/* 解题思路 使用滑动窗口双指针维护一个连续区间[left, right]。 1. right 指针不断向右扩展窗口 并统计当前字符出现的次数。 2. 如果当前字符出现重复 说明窗口不合法此时移动 left 缩小窗口 直到窗口重新变成无重复字符。 3. 在窗口合法的过程中 不断更新最长子串长度。 由于 left 和 right 都只会向右移动一次 所以时间复杂度为 O(n)。 */ class Solution { public: int lengthOfLongestSubstring(string s) { // 数组模拟哈希表记录字符出现次数 int hash[128] {0}; // 滑动窗口左右边界 int left 0, right 0; int n s.size(); // 记录最长无重复子串长度 int ret 0; // 滑动窗口 while(right n) { // 当前字符进入窗口 hash[s[right]]; // 出现重复字符缩小窗口 while(hash[s[right]] 1) { // 左边界字符移出窗口 hash[s[left]]--; // 左边界右移 left; } // 更新最长长度 ret max(ret, right - left 1); // 扩大窗口 right; } return ret; } };没懂看看大神的解题代码大神解题代码class Solution { public: int lengthOfLongestSubstring(string s) { int hash[128] {0}; // 记录窗口内字符出现次数 int left 0, right 0; int ret 0; while(right s.size()) { hash[s[right]]; // 当前字符进入窗口 // 当前字符重复缩小窗口 while(hash[s[right]] 1) { hash[s[left]]--; left; } // 更新最长长度 ret max(ret, right - left 1); right; // 扩大窗口 } return ret; } };3最大连续1的个数 III⭐⭐题目链接最大连续1的个数 III解题思路题目要求我们求最长的连续 1 的个数并且最多可以将k个 0 翻转成 1。本质上就是在数组中维护一个合法区间因此可以使用滑动窗口双指针来解决。我们用left和right两个指针维护当前窗口并用变量zero记录窗口中 0 的个数。由于题目允许最多翻转k个 0因此当窗口内 0 的个数 k时当前窗口合法可以更新答案。当窗口内 0 的个数 k时当前窗口不合法需要移动left缩小窗口直到窗口重新合法。在整个过程中left和right都只会向右移动一次因此时间复杂度为O(n)。解题代码/* 解题思路 使用滑动窗口双指针维护一个连续区间[left, right]。 1. right 指针不断向右扩展窗口 并统计窗口内 0 的个数。 2. 当窗口内 0 的个数大于 k 时 说明当前窗口不合法 需要移动 left 缩小窗口。 3. 当窗口重新合法后 更新窗口的最大长度。 由于 left 和 right 都只会向右移动一次 所以时间复杂度为 O(n)。 */ class Solution { public: int longestOnes(vectorint nums, int k) { // left 和 right 为滑动窗口左右边界 int left 0; int right 0; // 记录窗口内 0 的个数 int zero 0; // 记录最长合法窗口长度 int retlen 0; // 滑动窗口 while(right nums.size()) { // 当前元素为 0 if(nums[right] 0) { zero; } // 窗口不合法缩小窗口 while(zero k) { // 左边界为 0窗口内 0 的个数减少 if(nums[left] 0) { zero--; } // 左边界右移 left; } // 更新最大长度 retlen max(retlen, right - left 1); // 扩大窗口 right; } return retlen; } };没懂看看大神的解题代码大神解题代码class Solution { public: int longestOnes(vectorint nums, int k) { int ret 0; // 记录窗口最大长度 // 滑动窗口left为左边界right为右边界 // zero记录窗口内0的个数 for(int left 0, right 0, zero 0; right nums.size(); right) { // 当前元素进入窗口 if(nums[right] 0) zero; // 窗口不合法缩小窗口 while(zero k) { // 左边界元素移出窗口 if(nums[left] 0) zero--; } // 更新最大长度 ret max(ret, right - left 1); } return ret; } };4将 x 减到 0 的最小操作数⭐⭐题目链接将 x 减到 0 的最小操作数解题思路题目要求我们每次从数组的最左边或者最右边删除元素并让这些被删除元素的和等于x。直接模拟删除会比较复杂因此我们可以换个角度思考删除左右两边元素的和为x等价于中间保留一段连续子数组其和为sum - x并且删除元素个数最少等价于保留的子数组长度最长因此问题就转换成求和为sum - x的最长连续子数组长度。由于数组中的元素都为正数因此可以使用滑动窗口解决。我们用left和right维护窗口并记录窗口元素和当窗口和大于 target 时缩小窗口。当窗口和等于 target 时更新最长子数组长度。最后操作次数 数组总长度 - 最长子数组长度。由于left和right都只会向右移动一次因此时间复杂度为O(n)。解题代码/* 解题思路 题目要求从数组左右两边删除元素 使删除元素之和等于 x。 可以转换思路 删除左右元素之和为 x 等价于保留中间一段连续子数组 其和为 sum - x。 因此问题转换成 求和为 target 的最长连续子数组长度。 最后 操作次数 数组总长度 - 最长子数组长度。 由于数组元素全为正数 可以使用滑动窗口解决。 */ class Solution { public: int minOperations(vectorint nums, int x) { // 计算数组总和 int sum 0; for(auto it : nums) { sum it; } // 目标窗口和 int target sum - x; // 总和小于 x无法完成操作 if(target 0) return -1; // 整个数组都需要删除 if(target 0) return nums.size(); // 滑动窗口左右边界 int left 0, right 0; // 当前窗口和 int tmp 0; // 记录最长合法窗口长度 int len 0; // 滑动窗口 while(right nums.size()) { // 当前元素进入窗口 tmp nums[right]; // 窗口和过大缩小窗口 while(tmp target) { tmp - nums[left]; left; } // 找到合法窗口 if(tmp target) { len max(len, right - left 1); } // 扩大窗口 right; } // 没有找到合法窗口 if(len 0) return -1; // 最少操作次数 return nums.size() - len; } };5水果成篮⭐⭐⭐题目链接水果成篮解题思路题目要求我们寻找一个最长的连续子数组并且这个子数组中最多只能包含两种水果。本质上就是求“至多包含两种元素”的最长连续区间。因此可以使用滑动窗口双指针解决。我们用left和right维护当前窗口并使用哈希表记录窗口中每种水果出现的次数。由于窗口中最多只能有两种水果当窗口内水果种类数 2时当前窗口合法可以更新答案。当窗口内水果种类数 2时当前窗口不合法需要移动left缩小窗口。在整个过程中left和right都只会向右移动一次因此时间复杂度为O(n)。解题代码/* 解题思路 使用滑动窗口双指针维护一个连续区间[left, right]。 1. right 指针不断向右扩展窗口 并统计窗口内水果出现次数。 2. 当窗口内水果种类超过 2 种时 说明当前窗口不合法 需要移动 left 缩小窗口。 3. 当窗口重新合法后 更新最长窗口长度。 由于 left 和 right 都只会向右移动一次 所以时间复杂度为 O(n)。 */ class Solution { public: int totalFruit(vectorint fruits) { // 滑动窗口左右边界 int left 0, right 0; // 哈希表记录水果出现次数 unordered_mapint, int mp; // 记录最长合法窗口长度 int len 0; // 滑动窗口 while(right fruits.size()) { // 当前水果进入窗口 mp[fruits[right]]; // 水果种类超过 2 种缩小窗口 while(mp.size() 2) { // 左边界水果移出窗口 mp[fruits[left]]--; // 数量为 0移除该水果 if(mp[fruits[left]] 0) { mp.erase(fruits[left]); } // 左边界右移 left; } // 更新最长长度 len max(len, right - left 1); // 扩大窗口 right; } return len; } };没懂看看大神的解题代码大神解题代码class Solution { public: int totalFruit(vectorint f) { unordered_mapint, int hash; // 统计窗口内水果数量 int ret 0; // 记录最长合法窗口长度 // 滑动窗口 // left 为左边界 // right 为右边界 for(int left 0, right 0; right f.size(); right) { // 当前水果进入窗口 hash[f[right]]; // 水果种类超过 2 种缩小窗口 while(hash.size() 2) { hash[f[left]]--; // 当前水果数量为 0移除 if(hash[f[left]] 0) { hash.erase(f[left]); } left; } // 更新最长长度 ret max(ret, right - left 1); } return ret; } };6找到字符串中所有字母异位词⭐⭐⭐题目链接找到字符串中所有字母异位词解题思路题目要求我们找到字符串s中所有与字符串p的字母异位词。所谓字母异位词就是两个字符串包含的字符种类和数量完全相同只是顺序不同。由于我们需要寻找的是长度固定为p.size()的连续子串。因此可以使用固定长度的滑动窗口来解决。我们使用两个哈希数组hash1记录字符串p中每个字符出现的次数。hash2记录当前窗口中每个字符出现的次数。同时使用count记录当前窗口中“有效字符”的数量。滑动窗口过程右边界进入窗口时更新字符出现次数。当窗口长度超过p.size()时左边界出窗口维持窗口长度固定。当有效字符数量等于p.size()时说明当前窗口就是一个字母异位词。由于每个字符最多进出窗口一次因此时间复杂度为O(n)。解题代码/* 解题思路 使用固定长度滑动窗口维护长度为 p.size() 的区间。 1. hash1 记录字符串 p 中字符出现次数。 2. hash2 记录当前窗口中字符出现次数。 3. count 记录窗口内有效字符数量。 4. 当窗口长度超过 p.size() 时 移动 left 缩小窗口。 5. 当 count p.size() 时 说明当前窗口为字母异位词。 时间复杂度为 O(n)。 */ class Solution { public: vectorint findAnagrams(string s, string p) { // 记录 p 中字符出现次数 int hash1[26] {0}; for(auto it : p) { hash1[it - a]; } // 保存答案 vectorint ret; // 记录窗口中字符出现次数 int hash2[26] {0}; // count 记录有效字符数量 for(int left 0, right 0, count 0; right s.size(); right) { // 当前字符进入窗口 hash2[s[right] - a]; // 当前字符属于有效字符 if(hash2[s[right] - a] hash1[s[right] - a]) { count; } // 窗口长度超过 p.size() if(right - left 1 p.size()) { // 左边界字符属于有效字符 if(hash2[s[left] - a] hash1[s[left] - a]) { count--; } // 左边界字符移出窗口 hash2[s[left] - a]--; // 缩小窗口 left; } // 当前窗口是字母异位词 if(count p.size()) { ret.push_back(left); } } return ret; } };没懂看看大神的解题代码大神解题代码class Solution { public: vectorint findAnagrams(string s, string p) { // cnt1 记录 p 中字符出现次数 int cnt1[26] {0}; // cnt2 记录窗口中字符出现次数 int cnt2[26] {0}; // 统计 p 中字符频率 for(char ch : p) { cnt1[ch - a]; } vectorint ret; // 固定长度滑动窗口 for(int left 0, right 0; right s.size(); right) { // 当前字符进入窗口 cnt2[s[right] - a]; // 窗口长度超过 p.size() if(right - left 1 p.size()) { // 左边界字符移出窗口 cnt2[s[left] - a]--; left; } // 判断当前窗口是否为字母异位词 if(cnt1 cnt2) { ret.push_back(left); } } return ret; } };7串联所有单词的子串⭐⭐⭐⭐题目链接串联所有单词的子串解题思路题目要求我们找到由words中所有单词按任意顺序拼接形成的子串。并且每个单词长度相同每个单词必须全部使用一次因此我们可以使用在这里插入代码片“固定步长滑动窗口”来解决。假设每个单词长度为n单词总数为m那么合法窗口长度一定为m /* n/* 解题思路 由于所有单词长度相同 因此可以使用固定步长滑动窗口。 1. 每次窗口移动一个单词长度。 2. mp1 记录 words 中单词出现次数。 3. mp2 记录当前窗口中单词出现次数。 4. count 记录当前窗口中有效单词数量。 5. 当窗口长度超过总长度时 移动 left 缩小窗口。 6. 当 count words.size() 时 当前窗口为合法答案。 由于需要处理不同起点 因此需要枚举 0 ~ n-1 的所有起点。 */ class Solution { // 获取从 j 开始长度为 n 的字符串 string gets(int j, int n, string s) { string tmp ; while(n--) { tmp s[j]; } return tmp; } public: vectorint findSubstring(string s, vectorstring words) { // 单词长度 int n words[0].size(); // 统计 words 中单词出现次数 unordered_mapstring, int mp1; for(auto it : words) { mp1[it]; } vectorint ret; // 枚举不同起点 for(int m 0; m n; m) { // 当前窗口单词统计 unordered_mapstring, int mp2; // 滑动窗口 for(int left m, right m, count 0; right n s.size(); right n) { // 当前单词进入窗口 string tmp s.substr(right, n); mp2[tmp]; // 当前单词有效 if(mp2[tmp] mp1[tmp]) { count; } // 窗口长度超过限制 if((right - left n) (words.size() * n)) { // 左边界单词移出窗口 string tmp2 gets(left, n, s); // 当前单词属于有效单词 if(mp2[tmp2] mp1[tmp2]) { count--; } mp2[tmp2]--; // 数量为 0 时移除 if(mp2[tmp2] 0) { mp2.erase(tmp2); } // 缩小窗口 left n; } // 找到合法窗口 if(count words.size()) { ret.push_back(left); } } } return ret; } };没懂看看大神的解题代码大神解题代码class Solution { public: vectorint findSubstring(string s, vectorstring words) { int n words[0].size(); // 每个单词长度 int m words.size(); // 单词数量 // 统计 words 中每个单词出现次数 unordered_mapstring, int target; for(auto word : words) { target[word]; } vectorint ret; // 枚举不同起点 for(int i 0; i n; i) { unordered_mapstring, int window; // 滑动窗口 // left 为左边界 // right 为右边界 // count 为有效单词数量 for(int left i, right i, count 0; right n s.size(); right n) { // 当前单词进入窗口 string word s.substr(right, n); window[word]; // 当前单词有效 if(window[word] target[word]) { count; } // 窗口长度超过要求 while(right - left n m * n) { // 左边界单词 string del s.substr(left, n); // 当前单词有效 if(window[del] target[del]) { count--; } // 左边界单词移出窗口 window[del]--; if(window[del] 0) { window.erase(del); } left n; } // 找到合法窗口 if(count m) { ret.push_back(left); } } } return ret; } };下期预告今天的分享就到这里下一期我们将一起学习二分算法结语本期内容就到这里啦欢迎大家在评论区一起交流讨论如果你也在为蓝桥杯/ACM备赛头疼或是准备算法面试找不到系统学习路径欢迎订阅我的「算法从入门到精通」专栏这里没有枯燥的理论堆砌只有完整的算法学习路线搭配精选梯度习题清晰思路解析帮你把每个算法学透、练熟。包教包会的我们一起在算法路上稳步进阶《网络安全从零到精通全套学习大礼包》96节从入门到精通的全套视频教程免费领取如果你也想通过学网络安全技术去帮助就业和转行我可以把我自己亲自录制的96节 从零基础到精通的视频教程以及配套学习资料无偿分享给你。网络安全学习路线图想要学习 网络安全作为新手一定要先按照路线图学习方向不对努力白费。对于从来没有接触过网络安全的同学我帮大家准备了从零基础到精通学习成长路线图以及学习规划。可以说是最科学最系统的学习路线大家跟着这个路线图学习准没错。配套实战项目/源码所有视频教程所涉及的实战项目和项目源码学习电子书籍学习网络安全必看的书籍和文章的PDF市面上网络安全书籍确实太多了这些是我精选出来的面试真题/经验以上资料如何领取术去帮助就业和转行我可以把我自己亲自录制的96节 从零基础到精通的视频教程以及配套学习资料无偿分享给你。网络安全学习路线图想要学习 网络安全作为新手一定要先按照路线图学习方向不对努力白费。对于从来没有接触过网络安全的同学我帮大家准备了从零基础到精通学习成长路线图以及学习规划。可以说是最科学最系统的学习路线大家跟着这个路线图学习准没错。配套实战项目/源码所有视频教程所涉及的实战项目和项目源码学习电子书籍学习网络安全必看的书籍和文章的PDF市面上网络安全书籍确实太多了这些是我精选出来的面试真题/经验以上资料如何领取