本文共 1909 字，大约阅读时间需要 6 分钟。
滑动窗口思想在字符串处理问题中是一个非常经典且高效的方法。以下将详细介绍一种解决最小窗口子字符串包含问题的滑动窗口算法。
给定两个字符串 s 和 t，其中 t 是 s 的子字符串。我们需要找到 s 中最小的窗口子字符串，使得这个窗口中包含所有在 t 中出现的字符，并且每个字符的出现次数满足 t 中的要求。
这个算法采用了滑动窗口的双指针技术，通过维护一个字符频率字典来跟踪当前窗口中各字符的出现情况。具体步骤如下：
字符频率字典初始化：首先，我们初始化一个空的字符频率字典 t_dict，用于记录 t 中字符的频率。
遍历字符串 s：通过遍历字符串 s，我们逐步扩展窗口，并更新字符频率字典。
滑动窗口调整：当当前窗口中包含了所有 t 中的字符时，我们尝试收缩窗口以找到最小的有效窗口。每次收缩窗口时，我们检查当前窗口是否仍然满足包含所有 t 中字符的条件。
记录最小窗口：在整个遍历过程中，记录最小的满足条件的窗口位置和长度。
以下是实现该算法的代码：
class Solution: def minWindow(self, s: str, t: str) -> str: def is_equal(d1, d2): for key in d1: if d2.get(key, 0) < d1[key]: return False return True t_dict = {} for char in t: if char in t_dict: t_dict[char] += 1 else: t_dict[char] = 1 tmp_dict = {} for key in t_dict.keys(): tmp_dict[key] = 0 start = 0 res_start = -1 ans_length = len(s) for i in range(len(s)): if s[i] in t_dict: tmp_dict[s[i]] = tmp_dict.get(s[i], 0) + 1 while is_equal(t_dict, tmp_dict): current_window_length = i - start + 1 if current_window_length < ans_length: ans_length = current_window_length res_start = start if s[start] in tmp_dict: tmp_dict[s[start]] -= 1 start += 1 if res_start == -1: return "" return s[res_start:res_start + ans_length] is_equal 函数：用于检查两个字符频率字典是否相等。主要用于判断当前窗口是否包含所有 t 中的字符，并且频率满足要求。
t_dict 初始化：首先遍历 t 字符串，统计每个字符的频率，并存储在 t_dict 中。
tmp_dict 初始化：创建一个空的字符频率字典 tmp_dict，用于跟踪当前窗口中的字符频率。
主遍历逻辑：通过遍历 s 字符串，逐步扩展窗口。每次遇到 t 中字符时，更新 tmp_dict。
滑动窗口调整：当满足包含所有 t 中字符的条件时，尝试收缩窗口。每次收缩窗口时，检查是否仍然满足条件，并记录最小的有效窗口。
结果处理：如果没有找到满足条件的窗口，返回空字符串。否则，返回最小窗口对应的子字符串。
这种滑动窗口算法通过双指针技术和字符频率统计，能够在 O(n) 时间复杂度内解决问题，非常适合处理类似的问题。
转载地址：http://ubsl.baihongyu.com/