这种题就是典型的使用双指针法或者说滑动窗口法解决的题目，稍微看了一下别人的思路然后自己写了一下，写得有点丑陋感觉。首先，我们用defaultdict基于t初始化需要被包含的字符这样可以在遍历s中的字符时检查哪个字符还需要或者哪个字符已经多余了。这个defaultdict中t中包含的字符的个数都随着遍历慢慢减为1时我们知道滑动的窗口就包含所有t中的字符了，我们可以遍历一遍defaultdict来判断。但是这样遍历造成了浪费，因此我们可以用一个all_chars来记录，每被包含进一个t中的字符我们就将all_chars减1，当all_chars为0时说明所有t中的字符都被包含进去了。但此时，我们只是求出了一对滑动窗口的左右边界，为了找到最小的窗口长度，我们要收缩左边界即向左移动左指针。此时，当left跨过第一个t中包含的字符时，我们增加all_chars的值，这时候，为了使得all_chars重新变为0即滑动窗口再次包含t中所有的字符，我们要再次将right右指针向右边移动，以此类推求出最终的结果。另外，注意到在最终打印出结果的时候要判断一下ans这个元祖里的元素有无被更新过，如果一次都没有那我们就要返回“”来表示没有找到可以包含t的窗口。这个算法的时间复杂度是O（N），空间复杂度是O（C）常数级别也就是O（1）。
from collections import defaultdict
class Solution:
def minWindow(self, s: str, t: str) -> str:
t_chars = defaultdict(int)
for x in t:
t_chars[x] += 1
all_chars = len(t)
left, right = 0, 0
ans = (0, float("inf"))
while right < len(s):
if t_chars[s[right]] > 0:
all_chars -= 1
t_chars[s[right]] -= 1
while all_chars == 0:
tmplen = right - left + 1
if tmplen < (ans[1] - ans[0] + 1):
ans = (left, right)
if t_chars[s[left]] == 0:
all_chars += 1
t_chars[s[left]] += 1
left += 1
right += 1
return "" if ans[1] > len(s) else s[ans[0]:ans[1]+1]PREVIOUSlc042.接雨水
NEXTlc146.LRU缓存机制