Leetcode上有几道典型的滑动窗口的问题,笔者”labuladong”总结了几行代码的框架,很受益。
打油诗
滑动窗口解题逻辑框架:
/* 滑动窗口算法框架 */
void slidingWindow(string s, string t) {
unordered_map<char, int> need, window;
for (char c : t) need[c]++;
int left = 0, right = 0;
int valid = 0;
while (right < s.size()) {
// c 是将移入窗口的字符
char c = s[right];
// 右移窗口
right++;
// 进行窗口内数据的一系列更新
...
/*** debug 输出的位置 ***/
printf("window: [%d, %d)\n", left, right);
/********************/
// 判断左侧窗口是否要收缩
while (window needs shrink) {
// d 是将移出窗口的字符
char d = s[left];
// 左移窗口
left++;
// 进行窗口内数据的一系列更新
...
}
}
}
- LeetCode 76,Minimum Window Substring, Hard,中低频
string minWindow(string s, string t) {
unordered_map<char,int> need;
unordered_map<char,int> window;
for(auto c:t){
need[c]++;
}
int left=0;
int right=0;
int valid=0;
string ret;
int len=s.length();
while(right<s.length()){
char c=s[right];
right++;
if(need.count(c)!=0){
window[c]++;
if(window[c]==need[c]){
valid++;
}
}
//cout << left << "," << right << "," <<valid << "," <<need.size() << endl;
while(valid==need.size()){
if(right-left<=len){
len=right-left;
ret=s.substr(left,len);
}
char d=s[left];
left++;
if(need.count(d)!=0){
if(need[d]==window[d]){
valid--;
}
window[d]--;
}
}
}
return ret;
}
- LeetCode 567 ,Permutation in String, Medium
bool checkInclusion(string t, string s) {
unordered_map<char,int> need;
unordered_map<char,int> window;
for(auto c:t){
need[c]++;
}
int left=0;
int right=0;
int valid=0;
while(right<s.length()){
char c=s[right];
right++;
if(need.count(c)!=0){
window[c]++;
if(need[c]==window[c]){
valid++;
}
}
while(valid==need.size()){
if(right-left==t.size()){
return true;
}
char d=s[left];
left++;
if(need.count(d)!=0){
if(need[d]==window[d]){
valid--;
}
window[d]--;
}
}
}
return false;
}
- LeetCode 438 ,Find All Anagrams in a String, Medium,低频
这个所谓的字母异位词,就是排列,搞个高端的说法就能糊弄人而已,上一题稍微改改就好。
vector<int> findAnagrams(string s, string t) {
vector<int> ret;
if(s.empty()||t.empty()){
return ret;
}
if(s.length()<t.length()){
return ret;
}
unordered_map<char,int> need;
unordered_map<char,int> window;
for(auto c:t){
need[c]++;
}
int left=0;
int right=0;
int valid=0;
while(right<s.length()){
char c=s[right];
right++;
if(need.count(c)!=0){
window[c]++;
if(need[c]==window[c]){
valid++;
}
}
while(valid==need.size()){
if(right-left==t.size()){
ret.emplace_back(left);
}
char d=s[left];
left++;
if(need.count(d)!=0){
if(need[d]==window[d]){
valid--;
}
window[d]--;
}
}
}
return ret;
}