阅读量:0
写在前面：全部题都源于力扣
讲解
滑动窗口算法技巧主要用来解决子数组问题，比如让你寻找符合某个条件的最长/最短子数组。
如果用暴力解的话，你需要嵌套 for 循环这样穷举所有子数组，时间复杂度是O(n2)
for(int i = 0; i < nums.size(); i ++){ for(int j = i; j < nums.size(); j ++){ //维护一个nums[i,j]的子数组 } } 滑动窗口其实也并不难就是维护一个窗口，不断滑动，不断更新答案，大致逻辑：
int left = 0, right = 0; while (right < nums.size()) { // 增大窗口 window.addLast(nums[right]); right++; while (window needs shrink) { // 缩小窗口 window.removeFirst(nums[left]); left++; } } 由于这套逻辑left和right都不会回退，所以滑动窗口的时间复杂度是O(n)
没了，讲解到此结束
只学讲解是没有办法乱杀滴，接下来就靠着这个模板魔改解决hard题吧！
题目一：最小覆盖子串
力扣难度hard->传送门
滑动窗口的思路是这样的：
- 在字符串 S 中使用双指针中的左右指针技巧，初始化 left = right = 0，把索引左闭右开区间 [left, right) 称为一个「窗口」。
问：为什么设计为左闭右开区间？
答：因为这样初始化 left = right = 0 时区间 [0, 0) 中没有元素，但只要让 right 向右移动（扩大）一位，区间 [0, 1) 就包含一个元素 0 了。如果设置为两端都开的区间，那么让 right 向右移动一位后开区间 (0,1) 仍然没有元素；如果设置为两端都闭的区间，那么初始区间 [0, 0] 就包含了一个元素。这两种情况都会给边界处理带来不必要的麻烦。
- 先不断地增加 right 指针扩大窗口 [left, right)，直到窗口中的字符串符合要求（包含了 t 中的所有字符）。
- 此时，我们停止增加 right，转而不断增加 left 指针缩小窗口 [left, right)，直到窗口中的字符串不再符合要求（不包含 t 中的所有字符了）。同时，每次增加 left，我们都要更新一轮结果
- 重复第 2 和第 3 步，直到 right 到达字符串 s 的尽头。
talk is cheap,show me the code！
首先，需要window和need两个哈希表，用来记录窗口中已有的字符和需要凑齐的字符
// 记录 window 中的字符出现次数 unordered_map<char, int> window; // 记录所需的字符出现次数 unordered_map<char, int> need; for(char c : t) need[c] ++; 现在开始套模板，只需要思考以下几个问题：
- 什么时候应该移动 right 扩大窗口？窗口加入字符时，应该更新哪些数据？
答：只要窗口内没有满足t字符都有的话就应该继续扩大窗口，窗口加入字符时，需要更新窗口大小(window++)，必备字符个数(window[c]++)，已满条件的字符数(valid++)。
while(right < s.size()){ char c = s[right];//加入滑动窗口的值 right ++;//窗口变大 //新加入的值是否需要,需要的话： if(need(c)){ window[c]++;//已有的必备值加加 if(window[c] == need[c]) valid++;//如果某个字符在此窗口已经满足条件，valid++ } }
- 什么时候窗口应该暂停扩大，开始移动 left 缩小窗口？从窗口移出字符时，应该更新哪些数据？
答：当 valid 满足 need 时应该收缩窗口，应该在收紧窗口的时候更新最终数据，更新窗口大小，更新valid(移除元素了，这里只可能减)，window[字符]数量，另外更新最小覆盖子串的起始位置。因为答案一定是在缩窗口的时候出现的，所以应该在这里更新len和start
// 判断左侧窗口是否要收缩 while (valid == need.size()) { // 在这里更新最小覆盖子串 if (right - left < len) { start = left; len = right - left; } // d 是将移出窗口的字符 char d = s[left]; // 缩小窗口 left++; // 进行窗口内数据的一系列更新 if (need.count(d)) { if (window[d] == need[d]) valid--; window[d]--; }
- 我们要的结果应该在扩大窗口时还是缩小窗口时进行更新？
答：一定是在缩小的时候
整体代码：
class Solution { public: string minWindow(string s, string t) { unordered_map<char, int> need, window; for (char c : t) { need[c]++; } int left = 0, right = 0; // 记录window中的字符满足need条件的字符个数 int valid = 0; // 记录最小覆盖子串的起始索引及长度 int start = 0, len = INT_MAX; while (right < s.size()) { // c 是将移入窗口的字符 char c = s[right]; // 扩大窗口 right++; // 进行窗口内数据的一系列更新 if (need.count(c)) { window[c]++; if (window[c] == need[c]) valid++; } // 判断左侧窗口是否要收缩 // 用while！！一种缩到不能再缩 while (valid == need.size()) { // 在这里更新最小覆盖子串 // 必须先将len记录下来再更新窗口大小 // 只有这样才能记录每一次合法len，然后更新 if (right - left < len) { start = left; len = right - left; } // d 是将移出窗口的字符 char d = s[left]; // 缩小窗口 left++; // 进行窗口内数据的一系列更新 if (need.count(d)) { if (window[d] == need[d]) valid--; window[d]--; } } } // 返回最小覆盖子串 // 等于INT_MAX的话返回的是""不是" " return len == INT_MAX ? "" : s.substr(start, len); } }; 题目二：字符串排列
力扣567
mid难度，s1是可以包含重复字符的哦
是明显的滑动窗口算法，相当给你一个 S 和一个 T，请问你 S 中是否存在一个子串，包含 T 中所有字符且不包含其他字符？
基本和题目一是一样的，只有几个地方需要注意：
- 本题移动 left 缩小窗口的时机是窗口大小大于 t.length() 时，因为排列嘛，显然长度应该是一样的。
- 当发现 valid == need.size() 时，就说明窗口中就是一个合法的排列，所以立即返回 true。至于如何处理窗口的扩大和缩小，和最小覆盖子串完全相同。
完整代码：
class Solution { public: bool checkInclusion(string t, string s) { unordered_map<char, int> need, window; for (char c : t) need[c]++; int left = 0, right = 0, valid = 0; while (right < s.size()) { char c = s[right++]; if (need.count(c)) { window[c]++; if (window[c] == need[c]) valid++; } while (right - left > t.size()) { // 严格大于，以便准确控制窗口大小 char d = s[left++]; if (need.count(d)) { if (window[d] == need[d]) valid--; window[d]--; } } // valid == need.size()！！！ if (right - left == t.size() && valid == need.size()) // 确保窗口大小严格等于t的长度 return true; } return false; } }; 题目三：找所有字母异位词
力扣438
异位词，就是排列啊，搞了个高端的说法，也糊弄不了我们这些绝顶聪明的娃
直接上代码
class Solution { public: vector<int> findAnagrams(string s, string t) { unordered_map<char, int> need, window; for (char c : t) { need[c]++; } int left = 0, right = 0; int valid = 0; // 记录结果 vector<int> res; while (right < s.size()) { char c = s[right]; right++; // 进行窗口内数据的一系列更新 if (need.count(c)) { window[c]++; if (window[c] == need[c]) { valid++; } } // 判断左侧窗口是否要收缩 while (right - left > t.size()) { char d = s[left]; left++; // 进行窗口内数据的一系列更新 if (need.count(d)) { if (window[d] == need[d]) { valid--; } window[d]--; } } if(right - left == t.size() && valid == need.size()){ res.push_back(left); } } return res; } }; 题目四：无重复字符的最长子串
力扣3.
这题在双指针里面用双指针解决过了
如果用滑动窗口的话也很容易
窗口缩的条件就是window[c] > 1，说明有重复了
和双指针思路一模一样
双指针：维护[j，i]数组
#include<bits/stdc++.h> using namespace std; const int N = 1e5 + 10; int a[N]; int s[N]; int main(){ int n; int r = 0; cin >> n; for(int i = 0, j = 0; i < n; i ++){ cin >> a[i]; s[a[i]] ++;//记录个数 while(s[a[i]] > 1){ -- s[a[j ++]]; } r = max(r, i - j + 1); } cout << r; } 滑动窗口：
class Solution { public: int lengthOfLongestSubstring(string s) { int left = 0; int right = 0; int r = 0; unordered_map<char, int> window; while(right < s.size()){ char c = s[right]; right++; window[c]++; while(window[c] > 1){ char d = s[left]; window[d]--; left++; } r = max(r, right - left); } return r; } }; 题目五：滑动窗口的最大值
经典滑动窗口，力扣239
又名单调队列的实现
和题目1~4不一样，这题滑动窗口大小固定，每一次的移动也固定，难点在于求最大值
这里实现队列，要有pop，push操作，因为题目的特殊性，再加个返回最大值的max操作
我们需要逐步实现这三个API
push：
push 方法依然在队尾添加元素，但是要把前面比自己小的元素都删掉
void push(int n) { // 将前面小于自己的元素都删除 while (!maxq.empty() && maxq.back() < n) { maxq.pop_back(); } maxq.push_back(n); } max：
如果每个元素被加入时都这样操作，最终单调队列中的元素大小就会保持一个单调递减的顺序，因此我们的 max 方法可以可以这样写：
int max() { // 队头的元素肯定是最大的 return maxq.front(); } pop：
pop 方法在队头删除元素 n：
void pop(int n) { if (n == maxq.front()) { maxq.pop_front(); } } 所以综合代码：
class slidingQueue{ private: deque<int> maxq; public: void push(int n){ while(!maxq.empty() && n > maxq.back()) maxq.pop_back(); maxq.push_back(n); } int max(){ return maxq.front(); } void pop(int n){ if(!maxq.empty() && maxq.front() == n) maxq.pop_front(); } }; class Solution { public: vector<int> maxSlidingWindow(vector<int>& nums, int k) { slidingQueue window; vector<int> res; for(int i = 0; i < nums.size(); i ++){ if(i < k - 1){ window.push(nums[i]); } else{ window.push(nums[i]); res.push_back(window.max()); window.pop(nums[i - k + 1]); } } return res; } }; 