原题目:https://leetcode-cn.com/problems/minimum-window-substring/
思路:
滑动窗口的题目使用双指针的套路,一个指针用来扩大窗口,另一个指针用来缩小窗口。每一个时刻都只有一个指针移动,
本题之中,如果窗口不包含t的所有字母,进行窗口扩大,直到包含。
如果包含t中所有的 字母,进行窗口缩小,直到不包含。
记录最小len的left的位置就可以了
代码:
class Solution {
public:
unordered_map<char,int> ori,cnt;
bool check(){
for(const auto&p:ori){
if(cnt[p.first]<p.second){
return false;
}
}
return true;
}
string minWindow(string s, string t) {
for(const char&p : t){
ori[p]++;
}
int l=0,r=-1;
int len = INT_MAX,left=-1;
while(r<int(s.size())){
if(ori.find(s[++r])!=ori.end()){
cnt[s[r]]++;
}
while(check()&&l<=r){
if(r-l+1<len){
left=l;
len = r-l+1;
}
if(ori.find(s[l])!=ori.end()){
cnt[s[l]]--;
}
++l;
}
}
return left==-1? "":s.substr(left,len);
}
};