题目
题目地址：LeetCode 76:Minimum Window Substring
思路
我们可以使用双指针实现滑动窗口来在O（n）的时间复杂度解决这道题。
具体做法如下：
- 先扫描一边T，把对应的字符及其出现的次数存到哈希表中
- 用一个count来记录当前T中还有多少个字母未匹配，用start和end分别表示滑动窗口的左边界和右边界
- 开始遍历S，先向右移动窗口的右边界end，把遍历到的字母对应的哈希表中的value-1，如果减了1后value>=0说明该字母已经匹配完，count–
- 当count == 0时说明T中所有字符全部匹配完，此时滑动左窗口，寻找以当前end为右边界的最小窗口子串。我们用head和length来表示最小窗口子串的头部和长度，每次更新这两个值。在滑动左边界start时，每遍历到一个字母便把该字母在哈希表中的value+1（这是因为我们在加入字母到窗口时对哈希表-1，所以在从窗口中移除字母时需要对哈希表+1）。如果+1后value>0说明该字母在T中出现过，则未匹配字母数+1即count+1
- 重复这个过程直到end遍历到S的最后一个字母且count=0
有人可能会问到：对于不在T串中的字母的映射值也这么加呀减呀的，真的没问题吗？其实对于不在T串中的字母，我们减了1之后value变成-1，此时count不会增加，同理+1后valu为0，count也不会减少。而只有count的变化才会影响我们的最终结果，所以并没有什么关系。
代码
C++版本如下：
class Solution {
public:
string minWindow(string s, string t) {
unordered_map<char,int> m;
for(int i = 0;i < t.size();i++){
m[t[i]]++;
}
int start = 0,end = 0;//窗口左边界和右边界
int length = INT_MAX;//最小子串长度
int head = 0;//最小子串起点
int count = t.size();//记录t中还有多少个字母未匹配
for(int end = 0;end < s.size();end++){
//滑动右边界直到t中字母全部匹配完
if(--m[s[end]] >= 0){
count--;
}
//滑动左边界找以当前end为右边界的最小子串
while(count == 0){
//更新最小子串长度和最小子串的起点
if(end - start + 1 < length){
length = end - start + 1;
head = start;
}
//如果滑过的字母在t中出现过，则未匹配字母数+1
if(++m[s[start]] > 0){
count++;
}
start++;
}
}
return length == INT_MAX ? "" : s.substr(head,length);
}
};
Python版本如下：
class Solution(object):
def minWindow(self, s, t):
"""
:type s: str
:type t: str
:rtype: str
"""
m = collections.Counter(t)
count = len(t)
start = end = head = 0
length = sys.maxsize
while end < len(s) :
if m[s[end]] > 0 :
count -= 1
m[s[end]] -= 1
end += 1
while count == 0 :
if end - start < length :
length = end - start
head = start
if m[s[start]] == 0 :
count += 1
m[s[start]] += 1
start += 1
if length == sys.maxsize :
return ""
else :
return s[head:head + length]
