题意ref{:target=”_blank”}
滑动窗口的经典题目,大致思路
1. 遍历,右窗口滑动一个
2. 判断窗口长度符合的情况下(一般是两个指针间距离等于窗口距离),判断窗口内是否满足性质,生成答案
3. 左边窗口滑动
优化点:
在上面第二步判断是否满足性质的情况,如果数据过多,性质的判断较多,需要遍历一遍窗口内数据
一种优化方法是,使用cnt来标记需要满足要求的字符的数量,然后每次判断该数量的变化。在本题的情况下,滑动窗口每次移动只会增一个,删一个字符,临界点是两个map的字符数量相等时候。
1. 如果变化前相等,则cnt–,因为无论增删,都会导致cnt–
2. 如果变化后相等,则cnt++, 表示增删后,增加了一个满足性质的字符
C++ 代码
优化算法
class Solution {
public:
bool checkInclusion(string s1, string s2) {
for(char c:s1) m1_[c]++;
int n = s1.size();
int need = m1_.size();
for(int i=0, j=0,cnt=0; i<s2.size(); ++i) {
// 窗口右端点向右滑动 right++
char right = s2[i];
if(isEqual(right))cnt--;
m2_[right]++;
if(isEqual(right))cnt++;
// 注意这里是 i-j+1>n,因为right端点已经向右走了一步
if(i-j+1>n) {
char left = s2[j];
// 窗口左端点向右滑动 left++
if(isEqual(left))cnt--;
m2_[left]--;
if(isEqual(left))cnt++;
// left指针向右一步
j++;
}
if(cnt == need)return true;
}
return false;
}
private:
unordered_map<char, int> m1_, m2_;
bool isEqual(char c) {
if(m1_.count(c) && m1_[c] == m2_[c])return true;
return false;
}
};
普通算法
class Solution {
public:
bool checkInclusion(string s1, string s2) {
unordered_map<char, int> s1m, s2m;
for(char c:s1)s1m[c]++;
int n = s1.size();
for(int i=0; i<s2.size(); ++i) {
char c = s2[i];
s2m[c]++;
if(i>=n-1) {
bool is_ok = true;
for(auto item : s2m) {
char a = item.first;
int b = item.second;
if(b != s1m[a]){
is_ok = false;
break;
}
}
if(is_ok) return true;
s2m[s2[i+1-n]]--;
}
}
return false;
}
};