题目

给你一个字符串 S、一个字符串 T，请在字符串 S 里面找出：包含 T 所有字符的最小子串。

示例： 输入: S = “ADOBECODEBANC”, T = “ABC” 输出: “BANC” 说明：

如果 S 中不存这样的子串，则返回空字符串 “”。 如果 S 中存在这样的子串，我们保证它是唯一的答案。

思路

双指针滑窗法。 左右指针最开始都在0， 右指针遍历元素。每一次迭代都判断左右指针之间的字符是否已经包含了S中的字符，且数量是大于等于的。

碰到字符串，而且短时间无法想到解决办法，那就想尽办法用哈希。对于这道题，用两个哈希表。其中一个存T的字符以及对应的数目；另一个字符串存滑窗内部的且属于T中的字符串以及数目。

如果滑窗内部已经满足了条件，就看看长度是不是最小的。然后左指针向前，继续判断是不是满足条件。如果还满足，左指针继续向前；直到不满足，才移动右指针。所以for循环内部有个while循环。

class Solution: def minWindow(self, s: str, t: str) -> str: ori = {} cnt = {} for a in t: temp = ori.get(a, 0) ori[a] = temp + 1 left = 0; right = float('inf') ans_left = 0 n = len(s) for i in range(n): if s[i] in ori: temp = cnt.get(s[i], 0) cnt[s[i]] = temp + 1 while self.check(ori, cnt) and left <= i: # 滑窗内满足条件 if i - left + 1 < right - ans_left+1: # 更新最小串位置 right = i ans_left = left if s[left] in ori: # 左指针前移，对应的数量发生减一。 cnt[s[left]] -= 1 left += 1 if right == float('inf'): return "" return s[ans_left:right+1] def check(self, ori, cnt): for k,v in ori.items(): if not cnt.get(k, None): return False if cnt[k] < v: return False return True