76. 最小覆盖子串

https://leetcode-cn.com/problems/minimum-window-substring/

解法一：滑动窗口

将t的字符存入字典map中，t中未出现而s中出现的词频设为0。这样的目的是t要求的字符词频为正数。

（贪心法？）由于题目要求的只是‘包含’，用[begin…end]表示窗口，end先向前移动，用直方图法判断子串是否符合t。若符合，begin再向前压缩窗口。

class Solution:
    def minWindow(self, s: str, t: str) -> str:
		# 先统计词频，t中的字符词频大于0，在s中不在t中的等于0        
        map = dict()    
        for c in t:
            if c in map:
                map[c] += 1
            else:
                map[c] = 1
        for c in s:
            if c not in map:
                map[c] = 0

        count = 0  #表示匹配情况
        begin, end = 0, 0
        d = sys.maxsize  #记录窗口最小值
        head = 0  #记录最小窗口起始

        while end < len(s):
            if map[s[end]] > 0:  #只有遇到需要的字符（词频大于0的），count才计数
                count += 1
            map[s[end]] -= 1    #当前字符词频减1
            end += 1
            while count == len(t):  #若匹配，begin前移
                if end - begin < d:  #找到更小的窗口
                    d = end - begin
                    head = begin  
                if map[s[begin]] == 0:    #若移动处是需要的字符，修改count
                    count -= 1
                map[s[begin]] += 1
                begin += 1

        if d == sys.maxsize:    #若找不到
            return ""
        else:
            return s[head:head+d]

解法二：滑动窗口模板

方法一不适用于其他滑动窗口题，关键在于只用一个map无法准确描述匹配情况

import sys
class Solution:
    def minWindow(self, s: str, t: str) -> str:
        need={}
        window = {}
        for c in t:
            need[c] = need.get(c, 0)+1
        left=0      #窗口左边界
        right=0     #窗口右边界
        start=0     #记录子串起点
        minLen = sys.maxsize    #最小长度
        valid=0      #t串与s串匹配次数
        while right <len(s):
            #增大窗口
            c=s[right]
            right+=1
            if c in need:   #该字符在t串中
                window[c] = window.get(c, 0)+1
                if window[c] == need[c]:    #该字符匹配
                    valid +=1
            while valid==len(need):
                #更新
                if right-left < minLen:
                    minLen = right -left
                    start=left
                #缩小窗口，与增大窗口的操作对称
                d = s[left]
                left += 1
                if d in need:
                    if window[d] == need[d]:
                        valid -=1
                    window[d] -= 1

        return "" if minLen==sys.maxsize else s[start:start+minLen]