点击刷新
《滑动窗口防滑记》
---labuladong
滑动窗口老猛男，子串问题全靠他。
左右指针滑窗口，一前一后齐头进。
上面的打油诗节选自一个我很喜欢的博主东哥，生动凝练地概括了滑动窗口算法的精髓，
本文介绍的很棒的滑动窗口框架就是来自这位老哥的一篇公众号文章。
推荐给大家：https://mp.weixin.qq.com/s/ioKXTMZufDECBUwRRp3zaA
这里讨论的是使用一个滑动窗口框架解决字符串子串相关问题。字符串子串相关问题通常是，
在一个给定的字符串中（这里可以称之为母串），找到满足条件的子串，返回子串或者子串相关
的信息。
使用滑动窗口解决子串问题的一般思路就是：
1. 在母串中维护一个左开右闭的窗口 [left,right),窗口初始化为[0,0),此时窗口的长度为0，使用
合适的变量、数组、哈希表等记录 滑动过程中窗口的状态。
2. 让窗口的right 不断往右边移动 拉大窗口，每次移动都更新记录当前窗口的状态，当滑动窗口
对应的子串是题目的可行解时，就停止向右滑动，执行 第 3 步。比如求的是满足某个条件的最小子串，所有满足
该条件的子串都是可行解，其中最小的子串是最优解。
3. 在第 2 步right 停下来时，滑动窗口对应的子串是满足题目条件的一个可行解，这时让 left 也向右
滑动 缩小窗口，每次 left 移动之前 从 已有的可行解中 选取当前最优解。每次移动之后，更新记录当前窗口
的状态。移动之后，检查当前窗口对应的子串（ s.substr(left,right-left) ）是否还是可行解，是，继续移动；
不是，则停止移动 left, 跳回 第 2 步。
4. 重复第 2 和第 3 步，直到right到达字符串S的尽头。
具体来看 题目：
第 一 题： LeetCode 76 Minimum Window Substring， 最小覆盖子串 难度 Hard
整体代码如下：
1 string minWindow(string s, string t) { 2 unordered_map<char, int> need, window; 3 for (char c : t) need[c]++; 4 5 int left = 0, right = 0; 6 int valid = 0; 7 // 记录最小覆盖子串的起始索引及长度 8 int start = 0, len = INT_MAX; 9 while (right < s.size()) { 10 // c 是将移入窗口的字符 11 char c = s[right]; 12 // 右移窗口 13 right++; 14 // 进行窗口内数据的一系列更新 15 if (need.count(c)) { 16 window[c]++; 17 if (window[c] == need[c]) 18 valid++; 19 } 20 21 // 判断左侧窗口是否要收缩 22 while (valid == need.size()) { 23 // 在这里更新最小覆盖子串 24 if (right - left < len) { 25 start = left; 26 len = right - left; 27 } 28 // d 是将移出窗口的字符 29 char d = s[left]; 30 // 左移窗口 31 left++; 32 // 进行窗口内数据的一系列更新 33 if (need.count(d)) { 34 if (window[d] == need[d]) 35 valid--; 36 window[d]--; 37 } 38 } 39 } 40 // 返回最小覆盖子串 41 return len == INT_MAX ? 42 "" : s.substr(start, len); 43 }
思路分析：
1. 在母串 S 中维护一个左开右闭的窗口 [left,right),窗口初始化为[0,0),此时窗口的长度为0，这里使用两个哈希表和一个变量来记录
滑动窗口的状态：哈希表 need 中记录字符串 t 中所有字符和其出现次数，哈希表 window 中记录窗口含有 t 中的字符和其出现次数 ，
valid变量表示窗口中满足need条件的字符个数，如果valid 和 need.size 的大小相同，则说明窗口已满足条件，已经完全覆盖了串T。
1 unordered_map<char, int> need, window; 2 for (char c : t) need[c]++; 3 int valid = 0;
2. 让窗口的right 不断往右边移动 拉大窗口，每次移动 更新 need 和 valid, 如果valid 和 need.size 的大小相同，则说明窗口已满足条件，
停止移动right 。执行 第 3 步。
1 // c 是将移入窗口的字符 2 char c = s[right]; 3 // 右移窗口 4 right++; 5 // 进行窗口内数据的一系列更新 6 if (need.count(c)) { 7 window[c]++; 8 if (window[c] == need[c]) 9 valid++; 10 }
3. 在第 2 步right 停下来时，根据 valid == need.size() 条件 即当前 滑动窗口中是否已经包含了 t 中所有的字符，
判断左侧窗口是否要收缩，只要该条件成立就一直移动 left ，直到条件不成立了，立马退出循环，返回执行第二步。
在每次 移动 left 之前，更新最小覆盖子串：
1 // 在这里更新最小覆盖子串 2 if (right - left < len) { 3 start = left; 4 len = right - left; 5 }
在每次更新之后，更新窗口状态：
1 // d 是将移出窗口的字符 2 char d = s[left]; 3 // 左移窗口 4 left++; 5 // 进行窗口内数据的一系列更新 6 if (need.count(d)) { 7 if (window[d] == need[d]) 8 valid--; 9 window[d]--; 10 }
第 二 题： LeetCode 567 题，Permutation in String，难度 Medium：
分析：这题和第 1 题是一回事。求 s2 中是否包含 s1的排列，先 求 s2 中包含 s1 所有字符的最短子串，
如果求得的最短子串长度等于 s1.size() , 就包含，否则就不包含；
1 bool checkInclusion(string s1, string s2) { 2 return minWindow(s2,s1).size()==s1.size(); 3 }
第 三 题： LeetCode 第 438 题，Find All Anagrams in a String， 难度 Medium
分析：这题 仍然和第 1 题 是一回事 ，字符串 p 的 字母异位词，就是 p 的排列，就是一个东西 换了个说法。
代码如下：
1 vector<int> findAnagrams(string s, string t) { 2 unordered_map<char, int> need, window; 3 for (char c : t) need[c]++; 4 5 int left = 0, right = 0; 6 int valid = 0; 7 vector<int> res; // 记录结果 8 while (right < s.size()) { 9 char c = s[right]; 10 right++; 11 // 进行窗口内数据的一系列更新 12 if (need.count(c)) { 13 window[c]++; 14 if (window[c] == need[c]) 15 valid++; 16 } 17 // 判断左侧窗口是否要收缩 18 while (right - left >= t.size()) { 19 // 当窗口符合条件时，把起始索引加入 res 20 if (valid == need.size()) 21 res.push_back(left); 22 char d = s[left]; 23 left++; 24 // 进行窗口内数据的一系列更新 25 if (need.count(d)) { 26 if (window[d] == need[d]) 27 valid--; 28 window[d]--; 29 } 30 } 31 } 32 return res; 33 }
第四题 ： LeetCode 第 3 题，Longest Substring Without Repeating Characters，难度 Medium：
代码如下：
1 class Solution { 2 public: 3 int lengthOfLongestSubstring(string s) 4 { 5 int res = 0; 6 unordered_map<char,int> window; 7 int left = 0,right = 0; //[left,right) 8 while(left <= right && right < s.size()) 9 { 10 char c = s[right]; 11 // if(!window.count(c)) 12 if( window[c] == 0) 13 { 14 ++right; 15 res = max(res,right-left); 16 window[c]++; 17 } 18 else 19 { 20 char d = s[left]; 21 // if(window[d] > 0) 22 window[d]--; 23 ++left; 24 } 25 } 26 return res; 27 } 28 };
© 著作权归作者所有
发表评论
