最小窗口子串
一个滑动窗口的变形
string minWindow(string s, string t) {
vector<int> map(128,0);
for(auto ch : t)
++map[ch];//存储t中的字符个数
int counter = t.size();//目标字符串长度
int begin = 0, end = 0;
int head = 0;
int len = INT_MAX;
while(end < s.size())
{
/* 右边加,当这个字符是滑动窗缺少的字符时,计数器减一 */
//当滑动窗缺少时为正,富裕为负
if(map[s[end++]]-- > 0) --counter;
while(counter == 0)
{
if(end - begin < len)
{
len = end - begin;
head = begin;
}
/* 左边减,当这个字符是滑动窗不缺也不富余的字符时,计数器加一 */
if(map[s[begin++]]++ == 0) ++counter;
}
}
return len == INT_MAX ? "" : s.substr(head, len);
}