滑动窗口：解决最小覆盖子串问题

在字符串处理问题中，有一类经典问题是寻找满足特定条件的最小子串。今天我们来讨论一个典型的问题：最小覆盖子串。这个问题不仅考察了我们对字符串的处理能力，还涉及滑动窗口这一重要的算法思想。

---

问题描述

给定两个字符串 s 和 t，要求找到 s 中包含 t 所有字符的最短子串。如果 s 中不存在这样的子串，返回空字符串 ""。

示例

示例 1：

输入：s = "ADOBECODEBANC", t = "ABC"

输出："BANC"

解释："BANC" 是 s 中包含 t 所有字符的最短子串。

示例 2：

输入：s = "a", t = "a"

输出："a"

解释：整个字符串 s 就是最短子串。

示例 3：

输入：s = "a", t = "aa"

输出：""

解释：t 中有两个 'a'，但 s 中只有一个 'a'，无法满足条件。

---

解题思路 1. 滑动窗口

滑动窗口是一种经典的算法思想，特别适合处理子串或子数组问题。它的核心思想是通过维护一个窗口（通常用两个指针表示），在满足条件的情况下不断调整窗口的大小，从而找到最优解。

2. 具体步骤

统计字符频率：

使用一个哈希表（或数组）统计 t 中每个字符的出现次数。

例如，t = "ABC"，则哈希表为 {A:1, B:1, C:1}。

滑动窗口：

使用两个指针 left 和 right 表示窗口的左右边界。

右指针 right 向右移动，扩展窗口，直到窗口包含 t 的所有字符。

左指针 left 向右移动，收缩窗口，尝试找到更小的满足条件的子串。

记录结果：

在滑动窗口的过程中，记录满足条件的最短子串的起始位置和长度。

---

代码实现

以下是基于滑动窗口的 Java 实现：

import java.util.HashMap; import java.util.Map; class Solution { public String minWindow(String s, String t) { // 统计 t 中字符的频率 Map<Character, Integer> targetMap = new HashMap<>(); for (char c : t.toCharArray()) { targetMap.put(c, targetMap.getOrDefault(c, 0) + 1); } // 滑动窗口的字符频率 Map<Character, Integer> windowMap = new HashMap<>(); int left = 0; // 窗口左边界 int minLen = Integer.MAX_VALUE; // 最小子串长度 int start = 0; // 最小子串的起始位置 int count = 0; // 记录窗口中满足 t 字符条件的字符数量 for (int right = 0; right < s.length(); right++) { char currentChar = s.charAt(right); // 更新窗口字符频率 windowMap.put(currentChar, windowMap.getOrDefault(currentChar, 0) + 1); // 如果当前字符是 t 中的字符，并且窗口中的数量达到了 t 中的要求，则 count++ if (targetMap.containsKey(currentChar) && windowMap.get(currentChar).equals(targetMap.get(currentChar))) { count++; } // 当窗口满足 t 的所有字符条件时，尝试收缩窗口 while (count == targetMap.size()) { // 更新最小子串 if (right - left + 1 < minLen) { minLen = right - left + 1; start = left; } // 移动左边界，收缩窗口 char leftChar = s.charAt(left); windowMap.put(leftChar, windowMap.get(leftChar) - 1); // 如果左边界字符是 t 中的字符，并且窗口中的数量不再满足 t 的要求，则 count-- if (targetMap.containsKey(leftChar) && windowMap.get(leftChar) < targetMap.get(leftChar)) { count--; } left++; } } // 返回最小子串 return minLen == Integer.MAX_VALUE ? "" : s.substring(start, start + minLen); } } 代码解析

统计字符频率：

使用 targetMap 统计 t 中每个字符的出现次数。

滑动窗口：

使用 windowMap 记录当前窗口中每个字符的出现次数。

右指针 right 向右移动，扩展窗口。

当窗口满足 t 的所有字符条件时，尝试收缩窗口（移动左指针 left）。

更新最小子串：

在窗口满足条件时，记录当前窗口的长度和起始位置。

如果找到更小的窗口，则更新最小子串。

返回结果：

如果找到满足条件的最小子串，则返回该子串；否则返回空字符串。

---

复杂度分析

时间复杂度：O(m + n)，其中 m 是 s 的长度，n 是 t 的长度。滑动窗口的左右指针最多各遍历一次 s。

空间复杂度：O(m + n)，用于存储 targetMap 和 windowMap。

---

总结

最小覆盖子串问题是一个经典的滑动窗口问题。通过维护一个窗口，我们可以高效地找到满足条件的最小子串。滑动窗口的思想不仅适用于字符串问题，还可以用于数组、链表等其他数据结构的问题。希望这篇博客能帮助你更好地理解滑动窗口算法，并掌握解决类似问题的技巧！

如果你有任何问题或建议，欢迎在评论区留言！