动态滑动窗口还搞不清？一文搞定动态滑动窗口 | 基础算法

算法简述

如果做过双指针的相关题目，很容易理解最基础的滑动窗口算法：窗口长度固定，根据条件操作窗口的移动。但是真正有灵魂的滑动窗口算法，窗口大小是动态的。如果还不了解这个算法，跟着这篇博客便能轻松入门！

算法讲解

动态的窗口大小

一般来说，滑动窗口也是用两个指针来实现，实际解决问题时主要考虑的是元素如何入窗、出窗？滑动窗口一般会依赖于序列的特点，求解有关至少、至多的问题。所谓序列特点指当序列恰好满足题设条件时，更长（更短）的序列也满足要求。
由此，可以发现滑动窗口的本质就是在寻找那个恰好满足题设条件的序列【在危险的边缘反复横跳】。以求最小区间，至少元素等场景为例，指针的移动基本上遵循以下两点：

• 满足判定条件，左指针移动，老元素出窗
• 不满足判定条件，右指针移动，新元素入窗

相关问题

滑动窗口算法的应用场景有：

• 子数组/子串的最值问题（如最长无重复子串、最小覆盖区间）。
• 统计满足特定条件的连续子区间数量（如恰好/最多/最少包含k种元素）
  固定的窗口大小比较容易解决，动态的窗口大小可能需要转转变思考方式，具体会在下面的题目中分析。

题单

无重复字符的最长子串

int lengthOfLongestSubstring(string s) {unordered_map<char,int> m;int l = 0,r = 0;int n = s.size();int res = 0;while(r < n) {m[s[r]]++;// 当窗口内元素个数少于map的大小时// 必然存在重复的元素while(m.size() < r - l + 1){m[s[l]]--;if(m[s[l]] == 0){m.erase(s[l]);}l++;}res = max(res, r - l + 1);r++;}return res;
}

3306. 元音辅音字符串计数 II

恰好转化公式

根据下面这个公式，就能自由地将“恰好”问题转化为适合滑动窗口的“至多”或“至少问题。
$$\text{恰好k个元素}\equiv \text{至少k个元素}-\text{至少k+1个元素}\text{\hspace{1em}(1)}$$
$$\text{恰好k个元素}\equiv \text{至多k个元素}-\text{至多k-1个元素}\text{\hspace{1em}(2)}$$

该题中，我们使用公式（1）来转换问题。分别求每个元音字母至少出现一次且至少包含k和k+1个辅音字母的子串，然后相减即为所求。参考代码中使用map来统计子串的元音出现情况，题解中有“灵神”的更优解，使用数组与位运算来处理子串的元音信息

map<char,int> m;
bool check() {auto it = m.begin();while(it != m.end()) {if((*it).second < 1)return false;it++;}return true;
}long long cal(string& word, int k) {m['a'] = 0;m['i'] = 0;m['e'] = 0;m['o'] = 0;m['u'] = 0;int n = word.size();long long r = 0,l = 0;int cot = 0;long long res=0;while(r < n){if(m.find(word[r]) != m.end()){m[word[r]]++;}else{cot++;}while(check() && cot>=k){if(m.find(word[l]) != m.end()) {m[word[l]]--;}else {cot--;}l++;}res+=l;r++;}return res;
}long long countOfSubstrings(string word, int k) {return cal(word, k) - cal(word, k + 1);
}