76.最小覆盖子串题目来源：https://leetcode-cn.com/problems/minimum-window-substring题目给你一个字符串S，一个字符串T，请在字符串S中寻找：包含T所有字符的最小子串.例子：输入：S="ADOBECODEBANC",T="ABC"输出："BANC"解释：如果S中没有这样的子串，返回一个空串""。如果S中存在这样的子串，我们保证它是唯一的答案。解题思路：滑动窗口标题要求给定一个字符串S和一个字符串T，需要在字符串S中找到包含T的所有字符的最小子串，这里主要是找到最小子串。这部分的内容是我们需要维护和更新的。如果使用暴力破解，代码大致如下：foriinrange(len(S)):forjinrange(len(S)):ifS[i:j]containstheallthecharactersinT:update这部分的内存这里的时间复杂度是O(n^2)，不太理想。本文使用了滑动窗口的思想。这里使用双指针来达到一静一动查找的目的。大致思路如下：先初始化双指针，指向字符串S的起始位置（假设定义了left和right），那么区间[left,right)就是我们所说的窗口，我们控制通过移动指针来调整窗口的大小。（上面的区间是左闭右开，这里当指针一开始指向索引0时，因为右开，所以定义开始的部分是空区间。）接下来，我们移动先右指针（左指针不动），让它不断扩大窗口的大小，直到窗口包含字符串T中的所有字符。此时停止右指针移动，左指针移动。这时，窗口会缩小。当窗口中的字符串与字符串T中包含的所有字符都不匹配时，此时停止左指针的移动。这里，当你右指针停止移动再移动左指针时，记得更新结果（因为你要找到最小的子串）。现在只要重复上面的步骤2和3，直到右指针到达字符串S的末尾，程序就结束了。具体实现代码如下。代码实现类解决方案：defminWindow(self,s:str,t:str)->str:fromcollectionsimportdefaultdictwin=defaultdict(int)t_dict=defaultdict(int)foriint:t_dict[i]+=1#定义指针left=0right=0#初始化最小长度min_len=float('inf')#chr_count用于表示滑动窗口包含的字符数chr_count=0#最小子串起始位置begin=0#s长度s_len=len(s)#t长度t_len=len(t)whileright
