以s = "ADOBECODEBANC", t = "ABC"为例,进行如下演示
对于上图的说明:
1. 上面八个状态是在从左往右滑动窗口时,每发现一个窗口满足以下条件就进行状态暂停
条件:s[l, r] 覆盖了 t 这个字符串
2. 只有出窗口之后才有可能更新结果
滑动窗口需要问以下几个问题
Q1. 什么情况需要考虑开始从 r 所指的位置循环执行进窗口动作?
r 遍历到的当前字符是 s[r], 无论 s[r] 是否在 t中,都需要不断进窗口
Q2. 什么时候需要暂停执行进窗口动作?
r 遍历到的当前字符是 s[r], 无论 s[r] 是否在 t中,都需要不断进窗口
Q3. 什么时候需要考虑开始从 l 所指的位置循环执行出窗口动作?
当发现 s[l, r] 已经覆盖了 t 这个字符串
Q4. 什么时候需要暂停执行出窗口动作?
当发现 s[l] 存在于 t中,而且当前s[l, r]的中 s[l]的个数小于等于 t中 s[l]的个数
Q5. 什么时候更新结果?
当前窗口中包含了t中的所有字符时,更新结果
class Solution {
#define BIGINT -200000
public:
string minWindow(string s, string t) {
// record记录t中的某个字符还有多少个没被找到,
// 若为负数,表明当前的字符串中这个字符找多了
// unordered_map<char, int> record;
int record[58] = {BIGINT};
for(auto& ch : t){
if(record[ch - 'A'] < 0){
record[ch - 'A'] = 0;
}
record[ch - 'A']++;
}
int slen = s.size();
string ret;
int l = 0, r = 0;
while(r <= slen){
bool flag = false;
for(int i = 0; i < 58; ++i){
if(record[i] != BIGINT && record[i] > 0){
flag = true;
break;
}
}
if(flag == false){
while(record[s[l] - 'A'] == BIGINT || (record[s[l] - 'A'] != BIGINT && record[s[l] - 'A'] < 0)){
if(record[s[l] - 'A'] != BIGINT){
record[s[l] - 'A']++;
}
l++;
}
if(ret.size() == 0 || ret.size() > (r - l)){
ret.clear();
for(int i = l; i < r; ++i){
ret.push_back(s[i]);
}
}
}
if(r < slen && record[s[r] - 'A'] != BIGINT){
record[s[r] - 'A']--;
}
r++;
}
return ret;
}
};