1. 问题背景与核心挑战这道来自LeetCode的Hard题目要求我们在字符串S中找到包含字符串T所有字符的最短连续子串。举个例子如果SADOBECODEBANCTABC那么正确结果应该是BANC因为它同时包含A、B、C三个字母且长度最短。这个问题的难点在于如何高效处理两个字符串的字符匹配关系。暴力解法需要O(n²)时间复杂度——遍历所有可能的子串组合然后逐个检查是否包含T的所有字符。但在实际面试或竞赛中我们需要更聪明的解法。2. 滑动窗口算法解析2.1 基础滑动窗口实现滑动窗口Sliding Window是解决这类子串问题的经典方法。基本思路是维护一个可伸缩的窗口通过左右指针的移动来寻找最优解def minWindow(s: str, t: str) - str: from collections import defaultdict need defaultdict(int) for c in t: need[c] 1 need_cnt len(t) res (0, float(inf)) left 0 for right, c in enumerate(s): if need[c] 0: need_cnt - 1 need[c] - 1 if need_cnt 0: while True: c s[left] if need[c] 0: break need[c] 1 left 1 if right - left res[1] - res[0]: res (left, right) need[s[left]] 1 need_cnt 1 left 1 return s[res[0]:res[1]1] if res[1] ! float(inf) else 这个实现的时间复杂度确实是O(n)因为每个字符最多被左右指针各访问一次。空间复杂度是O(m)其中m是字符集大小。2.2 关键优化点解析哈希表的使用我们用need字典记录T中每个字符的需求量正数表示还需要多少个负数表示窗口中该字符有多余。need_cnt计数器这个变量记录当前还缺少多少个字符才能满足要求。当它归零时说明窗口已包含T的所有字符。左指针收缩当窗口满足条件时我们尝试左移左指针直到窗口刚好不满足条件为止这样可以找到当前右指针位置下的最短有效子串。3. 算法正确性证明要证明这个算法的正确性我们需要确认两点不会错过最优解当右指针移动到某个位置时左指针会收缩到尽可能靠右的位置确保记录的是当前最短有效子串。时间复杂度保证每个字符最多被左右指针各访问一次没有嵌套循环因此确实是O(n)时间复杂度。4. 实际编码中的陷阱4.1 字符计数处理一个常见的错误是没有正确处理字符计数。比如# 错误示例 if c in need: # 这样会漏掉need中计数为0的情况 need_cnt - 1正确的做法是直接检查need[c] 0因为我们的need字典会记录所有字符包括计数为0的。4.2 指针移动顺序另一个易错点是左指针移动时的顺序# 错误顺序 left 1 need[s[left]] 1 # 这里会漏掉最初的s[left]应该先处理当前left位置的字符再移动指针。5. 性能优化技巧5.1 提前终止当找到长度等于T长度的子串时可以直接返回因为不可能有更短的解if right - left 1 len(t): return s[left:right1]5.2 使用数组替代哈希表对于ASCII字符集可以用固定大小的数组代替哈希表减少哈希计算开销need [0] * 128 for c in t: need[ord(c)] 16. 复杂度对比方法时间复杂度空间复杂度适用场景暴力解法O(n²)O(m)不推荐滑动窗口O(n)O(m)推荐优化滑动窗口O(n)O(1)字符集固定时7. 扩展思考这个问题可以延伸出多个变种允许字符顺序不一致但必须连续允许部分字符缺失最多允许k个字符不匹配寻找包含T所有字符的最长子串而不是最短每种变种都可以基于滑动窗口的思想进行调整只需要修改窗口收缩的条件和结果记录方式。8. 实际应用场景这种算法在以下场景中非常实用文本编辑器的搜索高亮功能基因序列匹配网络流量模式识别数据流中的关键字检测掌握滑动窗口技巧不仅能解决这道LeetCode题目还能应对许多实际的字符串处理需求。我建议在理解基础解法后尝试自己实现几个变种问题这样可以更深入地掌握算法的核心思想。
1. 问题背景与核心挑战这道来自LeetCode的Hard题目要求我们在字符串S中找到包含字符串T所有字符的最短连续子串。举个例子如果SADOBECODEBANCTABC那么正确结果应该是BANC因为它同时包含A、B、C三个字母且长度最短。这个问题的难点在于如何高效处理两个字符串的字符匹配关系。暴力解法需要O(n²)时间复杂度——遍历所有可能的子串组合然后逐个检查是否包含T的所有字符。但在实际面试或竞赛中我们需要更聪明的解法。2. 滑动窗口算法解析2.1 基础滑动窗口实现滑动窗口Sliding Window是解决这类子串问题的经典方法。基本思路是维护一个可伸缩的窗口通过左右指针的移动来寻找最优解def minWindow(s: str, t: str) - str: from collections import defaultdict need defaultdict(int) for c in t: need[c] 1 need_cnt len(t) res (0, float(inf)) left 0 for right, c in enumerate(s): if need[c] 0: need_cnt - 1 need[c] - 1 if need_cnt 0: while True: c s[left] if need[c] 0: break need[c] 1 left 1 if right - left res[1] - res[0]: res (left, right) need[s[left]] 1 need_cnt 1 left 1 return s[res[0]:res[1]1] if res[1] ! float(inf) else 这个实现的时间复杂度确实是O(n)因为每个字符最多被左右指针各访问一次。空间复杂度是O(m)其中m是字符集大小。2.2 关键优化点解析哈希表的使用我们用need字典记录T中每个字符的需求量正数表示还需要多少个负数表示窗口中该字符有多余。need_cnt计数器这个变量记录当前还缺少多少个字符才能满足要求。当它归零时说明窗口已包含T的所有字符。左指针收缩当窗口满足条件时我们尝试左移左指针直到窗口刚好不满足条件为止这样可以找到当前右指针位置下的最短有效子串。3. 算法正确性证明要证明这个算法的正确性我们需要确认两点不会错过最优解当右指针移动到某个位置时左指针会收缩到尽可能靠右的位置确保记录的是当前最短有效子串。时间复杂度保证每个字符最多被左右指针各访问一次没有嵌套循环因此确实是O(n)时间复杂度。4. 实际编码中的陷阱4.1 字符计数处理一个常见的错误是没有正确处理字符计数。比如# 错误示例 if c in need: # 这样会漏掉need中计数为0的情况 need_cnt - 1正确的做法是直接检查need[c] 0因为我们的need字典会记录所有字符包括计数为0的。4.2 指针移动顺序另一个易错点是左指针移动时的顺序# 错误顺序 left 1 need[s[left]] 1 # 这里会漏掉最初的s[left]应该先处理当前left位置的字符再移动指针。5. 性能优化技巧5.1 提前终止当找到长度等于T长度的子串时可以直接返回因为不可能有更短的解if right - left 1 len(t): return s[left:right1]5.2 使用数组替代哈希表对于ASCII字符集可以用固定大小的数组代替哈希表减少哈希计算开销need [0] * 128 for c in t: need[ord(c)] 16. 复杂度对比方法时间复杂度空间复杂度适用场景暴力解法O(n²)O(m)不推荐滑动窗口O(n)O(m)推荐优化滑动窗口O(n)O(1)字符集固定时7. 扩展思考这个问题可以延伸出多个变种允许字符顺序不一致但必须连续允许部分字符缺失最多允许k个字符不匹配寻找包含T所有字符的最长子串而不是最短每种变种都可以基于滑动窗口的思想进行调整只需要修改窗口收缩的条件和结果记录方式。8. 实际应用场景这种算法在以下场景中非常实用文本编辑器的搜索高亮功能基因序列匹配网络流量模式识别数据流中的关键字检测掌握滑动窗口技巧不仅能解决这道LeetCode题目还能应对许多实际的字符串处理需求。我建议在理解基础解法后尝试自己实现几个变种问题这样可以更深入地掌握算法的核心思想。
