文章目录
题目描述思路分析步骤一：步骤二：步骤三：问题1：何时让count减一？问题2： 当count为0时，立即记录窗口长度值吗？问题3,：左边界left缩短的终止条件是什么？问题4：非条件值是否会影响left的终止条件？
完整代码
题目描述
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 “” 。 注意： 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。 如果 s 中存在这样的子串，我们保证它是唯一的答案。
示例 1： 输入：s = “ADOBECODEBANC”, t = “ABC” 输出：“BANC” 解释：最小覆盖子串 “BANC” 包含来自字符串 t 的 ‘A’、‘B’ 和 ‘C’。
示例 2： 输入：s = “a”, t = “a” 输出：“a” 解释：整个字符串 s 是最小覆盖子串。
示例 3: 输入: s = “a”, t = “aa” 输出: “” 解释: t 中两个字符 ‘a’ 均应包含在 s 的子串中， 因此没有符合条件的子字符串，返回空字符串。
思路分析
一道滑动窗口的题，不过归到了hard里，显然是有点弯弯绕绕在里面。
按步骤走先。
步骤一：
划定窗口的左右边界，left和right。 设置一个变量count来记录当前所需的字符。初始时count为字符串t的长度。
步骤二：
不断往右移动right，当count为0时，则表示当前窗口内的元素已经符合条件。
步骤三：
将left往右移动，减小窗口内的字符数量，将不必要的值扔掉，毕竟要求是最小的窗口长度嘛。
上述三步就是我一开始的思路，虽然我知道这道题肯定有点坑，没那么简单，但是还是按照上面这个思路写了一下，发现几个问题。
问题1：何时让count减一？
是碰到需要的字符就减1吗，显然不是，比如 s = ‘BECODEBANC’ t = ‘ABC’ 。count初始值为3。 可以看到，right不断从0开始往右走。当需要的字符A还没出现的时候，就已经出现了两次B和一次C了，这时候count已经为0。但此时窗口内的元素并不符合要求。 所以，需要一个辅助的哈希表来记录所需元素是否都已经符合要求了。 初始设置一个哈希表hs，遍历t来设置hs，本例中hs={‘A’: 1, ‘B’: 1, ‘C’: 1}。 right不断往右的过程中，遇到字符先判断hs里该值对应的value是否大于0，如果大于0，则表示是我们需要的值，此时再让count减一。 用上这个方法之后，再回头看刚才的例子。当出现第一个B的时候，他是我们需要的字符，则让hs[’ B ']-=1,计数器 ‘count-=1‘。此时哈希表中B字符对应的value就等于0了。当再次遇到第二个B的时候，哈希表中的B对应value为0，不满足大于0的要求，所以不减count。
问题2： 当count为0时，立即记录窗口长度值吗？
在第二步的时候，count为0了，虽然此时窗口内的长度已经覆盖了t，但是并不是要立即记录窗口的长度值。 比如 s = ‘BECODEBANC’ t = ‘ABC’
假设现在的left指向第一个B，也就是0号位置，right不断向右走，走到倒数第三个位置的A，此时窗口内包含ABC三个元素，这时候count=0了。但可以发现，窗口内含有两个B，左边的B是不必要的值。 为了减小窗口的长度符合题意，则尽量将左边界往右移动，缩短窗口长度。 此时就遇到了问题3.
问题3,：左边界left缩短的终止条件是什么？
从问题2可以看到，缩短左边界是在每一次记录前要做的事。 在解决这个问题之前，必须重申，hs表里记录的是每一个元素需要的次数。 比如 {‘A’: 1, ‘B’: 1, ‘C’: 1}),则表示A需要1次，B需要1次，C需要1。 如果{‘A’: 0。，C=‘-1’} 则表示A已经不需要了，刚好，而C多余一个。
hs表里记录的是每一个元素需要的次数！！！ hs表里记录的是每一个元素需要的次数！！！ hs表里记录的是每一个元素需要的次数！！！
牢记上面这句话。
所以在判断何时终止左边界的时候就非常好想了，如果碰到左边界的值在哈希表中的value为0了，则说明这个左边界的值是必须需要的，此时终止。
这时候left和right的窗口内所有元素都是需要的，此时记录，更新窗口的最短长度。
问题4：非条件值是否会影响left的终止条件？
本例中必须条件值是ABC，还有一个非条件值，DEON四个。 在程序运行过程中，非条件值也会被加入到哈希表中，那么DEON这四个非条件值会影响left的终止吗。 显然不会，因为哈希表本身就是记录所需元素的个数的，一开始，那些不需要的元素是没有进行初始化的，或者说初始化为0，遇到一个则变成-1。再看一遍那句话hs表里记录的是每一个元素需要的次数！！！秒懂！！结束。
完整代码
class Solution:
def minWindow(self, s: str, t: str) -> str:
import collections
hs = collections.defaultdict(int)
for i in t: # 先初始化t字符到哈希表中
hs[i] +=1
count = len(t)
res = [0,99999]
left = 0
right = 0
while right if hs[s[right]]>0: # 若哈希表中当前value大于0，则只可能是我们需要的字符 count-=1 hs[s[right]]-=1 if count == 0: while True: # 去掉左边多余的值 if hs[s[left]] == 0: break hs[s[left]] +=1 left +=1 if right-left < res[1] - res[0]: # 记录当前最大值 res[0], res[1] = left,right # 这时候的字符串状态是满足条件的，要移动左指针让他继续往右移动 hs[s[left]] +=1 count +=1 left+=1 right +=1 return ''if res[1]==99999 else s[res[0]:res[1]+1] 推荐链接
您阅读本篇文章共花了：
发表评论