记录一个题：
leetcode: 76. Minimum Window Substring
【最小覆盖子串例子解释】Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).也就是在S串中找到包含T串里所有字符的最小子串是哪里，T中有重复字符的话，也考虑重复的字符。
Input: S = “ADOBECODEBANC”, T = “ABC”
Output: “BANC”
- 解析：利用滑动窗口的思想来解决这个题，先不考虑最小的子串，对T中的所有字符建立一个hash字典，键为字符，值为字符出现的次数 ；然后遍历S，遇到在字典里的字符就减去1，若减去的次数等于T串长度，说明遍历到这里的时候该S里包含了T的子串；现在考虑最小子串，那么把之间得到的S遍历长度看做一个窗口，这个窗口需要不断的扩大右边，使得窗口里刚好装着T中所有的字符,从左到右遍历S的过程中把遍历位置处的字符的值（-1）表示遍历过了；这时候开始缩小窗口左边的位置，缩小的过程是把遍历过的位置复原（+1），直到我们遍历到第一个属于T中的字符（比如a），该位置复原完成后，这一轮缩小窗口的操作便结束了，下一次又是扩大右边的窗口，注意，关键的是下一次窗口满足装下T的所有字符的条件是遇到刚才的a字符，因为我们差的就是它；这样，窗口滑动到S串末尾，我们便可以得到最小覆盖的子串长度和它的开始位置。
- 其中S是输入串，T是要求覆盖的串，蓝色的区间表示该滑动窗口满足了T中的字符都被包含，接下来的一行是重置前面的字符直到遇到T中的字符；
- 接下来窗口右边往下继续扩展，知道遇到上一次移除的T字符A为止，然后左边又开始移动。。。。
最后窗口右边到达最后位置，窗口左边再次遍历得到最小的覆盖子串长度。
可以看出来时间复杂度是 O ( n ) O(n) O(n),通过记录窗口的左边并缩小，最多移动2n便可得到结果。
文章图片
class Solution {
public:
string minWindow(string s, string t) {
if (t.size() > s.size() || s.empty()) return "";
unordered_map table;
for (auto c : t) table[c]++;
int counter = t.size(), start = 0, end = 0, head = 0, minLen = INT_MAX;
while (end < s.size())
{
//如果这个数非零那就是出现在T中的字符啦
if (table[s[end]] > 0)counter--;
table[s[end]]--;
//不管s中end位置的字符出不出现都要递减1
end++;
//位置上升// 找到了一个有效窗口
while (counter == 0)
{
//记录所有有效窗口中最小的那个窗口的起点和长度
if (end - start < minLen)
{
minLen = end - start;
head = start;
}
//移动start寻找较小的窗口位置
table[s[start]]++;
if (table[s[start]] > 0) counter++;
start++;
}
}
return minLen == INT_MAX ? "" : s.substr(head, minLen);
}
};
