76. 最小覆盖子串 - 力扣LeetCode给定两个字符串s和t长度分别是m和n返回 s 中的最短窗口 子串使得该子串包含t中的每一个字符包括重复字符。如果没有这样的子串返回空字符串。测试用例保证答案唯一。示例 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 的子串中 因此没有符合条件的子字符串返回空字符串。提示m s.lengthn t.length1 m, n 105s和t由英文字母组成题目分析给定一个长串 s 和一个短串 t 要求找出 s 中包含 t 的最短字串。这题我们使用滑动窗口的思路从左往右一个个吃字母。首先为了保证子串最短子串最的起始元素一定是我们的目标元素同时 s 子串中包含 t 则需要保证 s 子串中对应 t 的字母和数量不小于 t 。因此我们会用到两张哈希表来分别记录目标串 t 的元素和个数以及当前子串的元素个数。到这里新的问题出现了如果每一次循环我们都要比较两张哈希表时间消耗会过大且代码过于复杂因此我们的判断方法转变成使用一个标量 v 来记录有多少个字母种类符合要求在扩展子串时就更新 v 当 v 符合要求时对当前子串进行记录判断当前子串是否为历史最优是则保留不是则舍去。实际代码中我们这一步要做的只是记录最短子串的头指针以及子串长度不需要切片等额外操作。代码思路# 两个指针进行滑动窗口# 我们先找齐一个满足题解的子串再不断地往右收缩直到最小# 相较于上面那个思路这里把收缩和查询拆分了开来找齐了再尝试收缩上面的思路则是一边找一边收缩感到复杂正常# 在这个思路中我们的判断方法转变成使用一个标量 v 来记录有多少个字母种类符合要求# 当然哈希表还是要用只不过直接比较的方法通过 v 来实现这样能避免很多不必要的麻烦# 开头我们使用字典 need 统计 t 的要求字符用空字典 have 统计已拥有的字符# 右指针扩展时不断的向 have 中添加字符当 have中的对应字符和need相等时v1# 当 v 达到上限时代表已经找到一个子串记录当前长度和起点下标进入收缩循环# 收缩循环内左指针不断右移两种可能# 1. 是need中的元素# 此时判断 have与need中的元素个数是否恰好等相等的情况下该字母移除会导致 v 减小不满足字符串自动退出循环# 不相等的情况下 have个数对应减小即可# 2. 不是need中的元素# 直接移动代码展示class Solution: def minWindow(self, s: str, t: str) - str: from collections import Counter have Counter() need Counter(t) # Counter的重要特征就是字典索引不存在的值不会报错可以避免代码中的逻辑判空 start 0 # 记录最短子串的起始点 left 0 right 0 valid 0 min_len float(inf) # 正无穷大保证能被比下去 for right, c in enumerate(s): if c in need: have[c] 1 if have[c] need[c]: valid 1 while valid len(need): # 此时找到子串 # 更新子串 if min_len right - left 1: min_len right - left 1 start left # 收缩子串 if s[left] in need: if have[s[left]] need[s[left]]: have[s[left]] - 1 valid - 1 else: have[s[left]] - 1 left 1 return if min_len float(inf) else s[start:startmin_len]