文章目录
1. 题目描述
给你一个字符串 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 中必须有两个 'a'，但 s 中只有一个 'a'，所以不存在符合要求的子串。
示例 4：
输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"
提示：
1 <= s.length, t.length <= 10^5s和t由英文字母组成
2. 理解题目
这道题要求我们在字符串 s 中找到一个最短的子串，该子串包含字符串 t 中的所有字符，且每个字符出现的次数不少于在 t 中出现的次数。
关键理解：
- 子串必须连续
- 子串需要包含
t中全部字符 - 如果
t中某字符出现多次，子串中该字符也必须出现相同或更多次 - 如果有多个满足条件的子串，返回最短的那个
- 如果
s中不存在满足条件的子串，返回空字符串
例如，对于示例1，s = "ADOBECODEBANC" 和 t = "ABC"：
- 子串
"ADOBEC"包含所有t中的字符 - 子串
"CODEBA"包含所有t中的字符 - 子串
"BANC"包含所有t中的字符，且是最短的符合条件的子串
因此答案是 "BANC"。
3. 解题思路
对于这种需要在字符串中寻找满足特定条件的子串的问题，滑动窗口是一种非常高效的解决方案。滑动窗口算法的基本思想是维护一个可变大小的窗口，通过不断调整窗口的左右边界，找到满足条件的最优解。
3.1 滑动窗口技术详解
滑动窗口是一种在数组或字符串上使用双指针的技术，通常用于解决连续子数组/子串相关的问题。它的核心思想是：
- 窗口定义：使用两个指针（通常命名为
left和right）来表示当前考虑的子数组或子串的边界，称为"窗口" - 窗口扩张：移动右指针扩大窗口，以纳入更多元素
- 窗口收缩：移动左指针缩小窗口，以排除元素
- 窗口状态：维护窗口内元素的状态信息（如计数、和等）
滑动窗口技术特别适合解决以下问题：
- 查找满足特定条件的连续子数组/子串
- 最长/最短的满足条件的子数组/子串
- 子数组/子串中的元素和或其他聚合值
3.1.1 滑动窗口模板
大多数滑动窗口问题可以按照以下模板来解决：
初始化左指针 left = 0
初始化右指针 right = 0
初始化窗口状态（如计数、和等）
初始化答案
while right < 数组或字符串长度:
// 扩大窗口
将右指针指向的元素纳入窗口
更新窗口状态
右指针右移 (right++)
while 窗口需要收缩的条件:
// 收缩窗口
更新答案（如果需要）
将左指针指向的元素移出窗口
更新窗口状态
左指针右移 (left++)
返回答案
这个模板的关键在于确定"窗口需要收缩的条件"，这通常是问题的核心。
3.2 本题的滑动窗口解法详解
针对最小覆盖子串问题，我们可以如下应用滑动窗口技术：
- 窗口定义：[left, right] 区间内的子串
- 窗口状态：当前窗口中各字符的出现次数，以及已经满足条件的目标字符的数量
- 扩张条件：当窗口不包含全部目标字符时
- 收缩条件：当窗口包含全部目标字符时，尝试通过移除左侧字符来最小化窗口
3.2.1 算法流程可视化
以示例 s = "ADOBECODEBANC", t = "ABC" 为例，展示算法流程：
初始状态：
A D O B E C O D E B A N C
↑
L,R
窗口：""
目标: A:1, B:1, C:1
窗口字符计数: {}
已满足字符数: 0
Step 1: 右指针右移一位，将 ‘A’ 纳入窗口
A D O B E C O D E B A N C
↑ ↑
L R
窗口："A"
目标: A:1, B:1, C:1
窗口字符计数: {A:1}
已满足字符数: 1 (A满足)
Step 2-6: 右指针继续右移，直到满足所有条件
A D O B E C O D E B A N C
↑ ↑
L R
窗口："ADOBEC"
目标: A:1, B:1, C:1
窗口字符计数: {A:1, D:1, O:1, B:1, E:1, C:1}
已满足字符数: 3 (A,B,C都满足)
Step 7: 满足条件后，尝试收缩窗口，移动左指针
A D O B E C O D E B A N C
↑ ↑
L R
窗口："DOBEC"
目标: A:1, B:1, C:1
窗口字符计数: {A:0, D:1, O:1, B:1, E:1, C:1}
已满足字符数: 2 (A不满足，B,C满足)
由于移除了 ‘A’，窗口不再满足条件，需要继续扩大窗口。
… (后续步骤省略)
最终找到的最小窗口是 “BANC”。
3.3 如何高效判断窗口是否包含所有目标字符？
判断窗口是否包含目标字符串中的所有字符是算法的关键部分。有几种方法可以实现这一判断：
3.3.1 方法一：哈希表计数比较
使用两个哈希表分别记录目标字符串和当前窗口中各字符的出现次数，然后遍历目标字符串的哈希表，检查每个字符在窗口中的出现次数是否足够。
优点：直观简单
缺点：每次判断需要遍历哈希表，效率较低
3.3.2 方法二：计数器
维护一个满足条件的字符种类计数器。当某个字符在窗口中的出现次数达到或超过在目标字符串中的出现次数时，计数器加1。当计数器等于目标字符串中不同字符的数量时，说明窗口满足条件。
优点：只需要比较计数器值，效率高
缺点：实现稍复杂，需要额外的变量和逻辑
3.3.3 方法三：差值计数
维护一个"还需要"的字符计数器。初始时，计数器为目标字符串的长度。每当窗口中某个字符的出现次数不超过目标字符串中的出现次数时，计数器减1。当计数器为0时，说明窗口满足条件。
优点：逻辑清晰，只需比较计数器是否为0
缺点：需要仔细处理重复字符
本文的实现主要使用方法二，通过跟踪已满足条件的不同字符数量来高效判断窗口是否包含所有目标字符。
4. 解法一：滑动窗口（HashMap实现）
4.1 算法步骤详解
预处理和边界检查：
- 检查输入字符串是否为空
- 检查源字符串长度是否小于目标字符串长度
- 初始化数据结构和变量
字符频率统计：
- 统计目标字符串中每个字符的出现频率
- 确定需要满足的不同字符数量
窗口扩张阶段：
- 移动右指针，将新字符纳入窗口
- 更新窗口中字符的频率统计
- 检查新加入的字符是否满足目标要求
- 更新已满足条件的字符数量
窗口收缩阶段：
- 当窗口满足所有条件时，尝试收缩窗口
- 记录当前满足条件的最小窗口
- 移动左指针，将字符移出窗口
- 更新窗口中字符的频率统计
- 检查移出的字符是否导致窗口不再满足条件
返回结果：
- 如果找到满足条件的窗口，返回最小窗口子串
- 否则返回空字符串
4.2 详细代码实现（带详细注释）
public class Solution {
public String minWindow(String s, String t) {
// 边界条件检查
if (s == null || t == null || s.length() == 0 || t.length() == 0 || s.length() < t.length()) {
return "";
}
// 创建两个哈希表，分别用于存储目标字符串和窗口中的字符频率
Map<Character, Integer> targetMap = new HashMap<>(); // 目标字符串中字符的频率
Map<Character, Integer> windowMap = new HashMap<>(); // 当前窗口中字符的频率
// 统计目标字符串中每个字符的出现频率
for (char c : t.toCharArray()) {
// getOrDefault 方法获取字符 c 的当前频率，如果不存在则默认为 0，然后加 1
targetMap.put(c, targetMap.getOrDefault(c, 0) + 1);
}
// 窗口的左右指针
int left = 0, right = 0;
// 记录已经满足条件的字符种类数量
// 例如，如果目标字符串中有字符 A:1, B:2, C:1
// 当窗口中含有 A:1, B:2, C:1 时，formed = 3（三种字符都满足）
int formed = 0;
// 记录最小窗口的起始位置和长度
// result[0] = 窗口长度，result[1] = 左边界，result[2] = 右边界
// 初始化 result[0] = -1，表示还未找到满足条件的窗口
int[] result = {-1, 0, 0};
// 主循环：扩展窗口直到找到包含所有目标字符的子串
while (right < s.length()) {
// 获取当前右边界的字符
char c = s.charAt(right);
// 更新窗口中字符的频率
windowMap.put(c, windowMap.getOrDefault(c, 0) + 1);
// 检查当前字符是否是目标字符，且窗口中的出现次数是否正好等于目标中的出现次数
// 注意这里使用 intValue() 进行值比较，避免 Integer 对象的引用比较
if (targetMap.containsKey(c) && windowMap.get(c).intValue() == targetMap.get(c).intValue()) {
// 如果满足条件，formed 加 1
formed++;
}
// 当窗口包含了所有目标字符（即 formed 等于目标字符的种类数），尝试收缩窗口
while (left <= right && formed == targetMap.size()) {
// 获取当前左边界的字符
c = s.charAt(left);
// 更新最小窗口
// 如果当前窗口比已记录的最小窗口更小，或者还未找到满足条件的窗口 (result[0] == -1)
if (result[0] == -1 || right - left + 1 < result[0]) {
// 更新最小窗口的信息
result[0] = right - left + 1; // 窗口长度
result[1] = left; // 左边界
result[2] = right; // 右边界
}
// 移除左边界的字符，准备收缩窗口
windowMap.put(c, windowMap.get(c) - 1);
// 检查移除的字符是否导致窗口不再满足条件
// 如果移除后窗口中该字符的出现次数小于目标字符串中要求的次数，则不再满足条件
if (targetMap.containsKey(c) && windowMap.get(c).intValue() < targetMap.get(c).intValue()) {
// 减少已满足条件的字符种类数
formed--;
}
// 移动左指针，继续尝试收缩窗口
left++;
}
// 移动右指针，扩大窗口
right++;
}
// 返回结果
// 如果 result[0] == -1，表示没找到满足条件的窗口，返回空字符串
// 否则，返回最小窗口子串
return result[0] == -1 ? "" : s.substring(result[1], result[2] + 1);
}
}
4.3 算法执行过程详解
以示例 s = "ADOBECODEBANC", t = "ABC" 进行详细分析：
初始化：
- targetMap = {A:1, B:1, C:1}
- windowMap = {}
- formed = 0
- left = 0, right = 0
- result = [-1, 0, 0]
迭代过程：
右指针 right = 0：
- 字符：‘A’
- 更新 windowMap = {A:1}
- ‘A’ 在 targetMap 中，且出现次数等于目标次数，formed = 1
- formed(1) < targetMap.size(3)，不进入内循环
- 右指针右移，right = 1
右指针 right = 1：
- 字符：‘D’
- 更新 windowMap = {A:1, D:1}
- ‘D’ 不在 targetMap 中，formed 不变
- formed(1) < targetMap.size(3)，不进入内循环
- 右指针右移，right = 2
… (过程略)
右指针 right = 5：
- 字符：‘C’
- 更新 windowMap = {A:1, D:1, O:1, B:1, E:1, C:1}
- ‘C’ 在 targetMap 中，且出现次数等于目标次数，formed = 3
- formed(3) == targetMap.size(3)，进入内循环
- 当前窗口 “ADOBEC”，长度为 6
- 更新 result = [6, 0, 5]
- 左指针左边字符：‘A’
- 更新 windowMap = {A:0, D:1, O:1, B:1, E:1, C:1}
- ‘A’ 在 targetMap 中，且出现次数小于目标次数，formed = 2
- formed(2) < targetMap.size(3)，跳出内循环
- 右指针右移，right = 6
… (过程略)
右指针 right = 11：
- 字符：‘N’
- 更新 windowMap = {A:1, B:1, C:0, D:0, E:0, O:0, N:1}
- ‘N’ 不在 targetMap 中，formed 不变
- formed(2) < targetMap.size(3)，不进入内循环
- 右指针右移，right = 12
右指针 right = 12：
- 字符：‘C’
- 更新 windowMap = {A:1, B:1, C:1, D:0, E:0, O:0, N:1}
- ‘C’ 在 targetMap 中，且出现次数等于目标次数，formed = 3
- formed(3) == targetMap.size(3)，进入内循环
- 当前窗口 “BANC”，长度为 4
- 更新 result = [4, 9, 12]
- … (内循环过程略)
- 右指针右移，right = 13，到达字符串末尾，退出主循环
返回结果：
- 找到的最小窗口是 “BANC”，长度为 4，起始位置为 9
- 返回 s.substring(9, 12 + 1) = “BANC”
4.4 复杂度分析详解
4.4.1 时间复杂度
总体时间复杂度：O(n + m)，其中 n 是字符串 s 的长度，m 是字符串 t 的长度。
详细分析：
- 预处理目标字符串
t，时间复杂度为 O(m)。 - 主循环中，右指针最多移动 n 次，左指针最多移动 n 次，每个字符最多被处理两次（一次加入窗口，一次移出窗口）。
- 哈希表操作（插入、查找、更新）的平均时间复杂度为 O(1)。
- 因此，主循环的时间复杂度为 O(n)。
4.4.2 空间复杂度
总体空间复杂度：O(k)，其中 k 是字符集的大小。
详细分析：
- targetMap 的大小取决于字符串
t中不同字符的数量，最多为 O(min(m, k))，其中 k 是字符集的大小。 - windowMap 的大小取决于窗口中不同字符的数量，最多为 O(min(n, k))。
- 其他变量（left, right, formed, result）使用常数空间。
- 由于字符集通常是有限的（如 ASCII 字符集或 Unicode 字符集），可以将 k 视为常数，空间复杂度可简化为 O(1)。但在最坏情况下，如果字符集非常大，空间复杂度仍为 O(k)。
4.4.3 优化空间
对于本题，如果已知字符集的大小（如只包含 ASCII 字符），可以使用数组代替哈希表，将空间复杂度的常数因子降低，同时提高查找和更新的效率。这种优化在方法二中有详细介绍。
5. 解法二：滑动窗口（数组优化版）
使用数组替代哈希表可以显著提高代码性能，特别是在处理字符集有限的情况下。
5.1 数组实现的优化思路
使用哈希表虽然灵活，但有以下缺点：
- 哈希表的操作（如put、get、containsKey）虽然平均时间复杂度为O(1)，但常数因子较大
- 哈希表需要额外的内存开销来维护内部结构（如桶、链表等）
- 哈希计算和冲突解决会带来额外的时间开销
当我们知道字符集有限（例如只包含ASCII字符或小写字母）时，可以使用整型数组来替代哈希表：
- 使用字符的ASCII码作为数组索引
- 直接通过索引访问和更新计数，避免哈希计算
- 数组的内存布局连续，可以更好地利用CPU缓存
5.2 优化的算法步骤详述
初始化两个计数数组：
targetCount[128]：存储目标字符串中每个字符的出现次数windowCount[128]：存储当前窗口中每个字符的出现次数
优化目标字符计数：
- 引入变量
requiredChars记录目标字符串中不同字符的数量 - 在统计目标字符串时，当某个字符第一次出现时，增加
requiredChars的值
- 引入变量
优化窗口状态判断：
- 引入变量
formedChars记录当前窗口中已经满足条件的不同字符的数量 - 当窗口中某个字符的出现次数正好等于目标中的出现次数时，增加
formedChars的值 - 当窗口中某个字符的出现次数从等于变为小于目标中的出现次数时，减少
formedChars的值 - 当
formedChars == requiredChars时，说明窗口包含了所有目标字符
- 引入变量
简化最小窗口记录：
- 使用
minLen和minStart两个变量记录最小窗口的长度和起始位置 - 不再使用数组存储这些信息
- 使用
5.3 详细代码实现与注释
public class Solution {
public String minWindow(String s, String t) {
// 边界条件检查 - 如果源字符串或目标字符串为空，或源字符串长度小于目标字符串长度，则无解
if (s == null || t == null || s.length() == 0 || t.length() == 0 || s.length() < t.length()) {
return "";
}
// 使用整型数组存储字符计数（使用ASCII码作为索引）
// ASCII字符集大小为128，覆盖了所有常见字符
int[] targetCount = new int[128];
int[] windowCount = new int[128];
// 统计目标字符串中每个字符的出现次数，并计算不同字符的数量
int requiredChars = 0; // 目标字符串中不同字符的数量
for (char c : t.toCharArray()) {
// 如果这个字符之前没出现过，增加不同字符的计数
if (targetCount[c] == 0) {
requiredChars++;
}
// 增加该字符的出现次数
targetCount[c]++;
}
// 初始化滑动窗口的左右指针
int left = 0, right = 0;
int formedChars = 0; // 已经满足条件的不同字符的数量
// 记录最小窗口的起始位置和长度
int minLen = Integer.MAX_VALUE; // 初始化为最大整数值
int minStart = 0; // 初始化最小窗口的起始位置
// 主循环：移动右指针扩大窗口
while (right < s.length()) {
// 获取当前右边界的字符，并更新窗口中的计数
char c = s.charAt(right);
windowCount[c]++;
// 检查当前字符是否是目标字符，且窗口中的出现次数是否正好等于目标中的出现次数
// 注意：必须是正好等于，不能是大于，因为我们要精确统计已满足条件的字符种类数
if (targetCount[c] > 0 && windowCount[c] == targetCount[c]) {
formedChars++;
}
// 当窗口包含了所有目标字符，尝试收缩窗口
// formedChars == requiredChars 意味着窗口中包含了目标字符串中的所有不同字符，且每个字符的出现次数不少于目标要求
while (left <= right && formedChars == requiredChars) {
// 更新最小窗口信息
if (right - left + 1 < minLen) {
minLen = right - left + 1;
minStart = left;
}
// 获取当前左边界的字符，准备将其移出窗口
c = s.charAt(left);
windowCount[c]--;
// 检查移除的字符是否导致窗口不再满足条件
// 这里的条件是：该字符是目标字符，且移除后窗口中该字符的出现次数小于目标要求
if (targetCount[c] > 0 && windowCount[c] < targetCount[c]) {
formedChars--;
}
// 移动左指针，继续尝试收缩窗口
left++;
}
// 移动右指针，扩大窗口
right++;
}
// 返回结果
// 如果minLen仍为Integer.MAX_VALUE，说明没找到满足条件的窗口，返回空字符串
// 否则，返回最小窗口子串
return minLen == Integer.MAX_VALUE ? "" : s.substring(minStart, minStart + minLen);
}
}
5.4 详细执行过程可视化
以示例 s = "ADOBECODEBANC", t = "ABC" 为例，展示使用数组优化的滑动窗口算法的执行过程：
初始化:
- targetCount = [0,0,…,A:1,B:1,C:1,…,0] (其中只有A、B、C的位置有值，其他都是0)
- windowCount = [0,0,…,0,0,0,…,0] (全部为0)
- requiredChars = 3 (目标字符串中有3个不同的字符：A、B、C)
- formedChars = 0
- left = 0, right = 0
- minLen = Integer.MAX_VALUE, minStart = 0
迭代过程:
right = 0: 字符 ‘A’
- 更新windowCount[A]++ = 1
- 判断: targetCount[A] = 1 > 0 且 windowCount[A] = 1 == targetCount[A] = 1
- formedChars++ = 1
- formedChars(1) < requiredChars(3)，不收缩窗口
- right++ = 1
right = 1: 字符 ‘D’
- 更新windowCount[D]++ = 1
- 判断: targetCount[D] = 0，不是目标字符
- formedChars = 1
- formedChars(1) < requiredChars(3)，不收缩窗口
- right++ = 2
right = 2: 字符 ‘O’
- 更新windowCount[O]++ = 1
- 判断: targetCount[O] = 0，不是目标字符
- formedChars = 1
- formedChars(1) < requiredChars(3)，不收缩窗口
- right++ = 3
right = 3: 字符 ‘B’
- 更新windowCount[B]++ = 1
- 判断: targetCount[B] = 1 > 0 且 windowCount[B] = 1 == targetCount[B] = 1
- formedChars++ = 2
- formedChars(2) < requiredChars(3)，不收缩窗口
- right++ = 4
right = 4: 字符 ‘E’
- 更新windowCount[E]++ = 1
- 判断: targetCount[E] = 0，不是目标字符
- formedChars = 2
- formedChars(2) < requiredChars(3)，不收缩窗口
- right++ = 5
right = 5: 字符 ‘C’
更新windowCount[C]++ = 1
判断: targetCount[C] = 1 > 0 且 windowCount[C] = 1 == targetCount[C] = 1
formedChars++ = 3
formedChars(3) == requiredChars(3)，开始收缩窗口
进入收缩循环:
当前窗口: “ADOBEC”, 长度为6
更新minLen = 6, minStart = 0
left = 0: 字符 ‘A’
- 更新windowCount[A]-- = 0
- 判断: targetCount[A] = 1 > 0 且 windowCount[A] = 0 < targetCount[A] = 1
- formedChars-- = 2
- formedChars(2) < requiredChars(3)，退出收缩循环
right++ = 6
… (后续迭代过程省略)
最终结果:
- 最小窗口长度: minLen = 4
- 最小窗口起始位置: minStart = 9
- 最小窗口: s.substring(9, 9+4) = “BANC”
5.5 性能分析与基准测试
5.5.1 数组vs哈希表性能对比
在实际应用中，基于数组的实现相比基于哈希表的实现有显著的性能优势：
| 实现方式 | 平均运行时间 | 内存使用 |
|---|---|---|
| 哈希表 | 100% | 100% |
| 数组 | 约60-80% | 约70-90% |
注：百分比表示相对于哈希表实现的比例，数值越小表示性能越好
这种性能差异在输入规模较大时更加明显。
5.5.2 性能差异原因分析
访问效率：
- 数组通过索引直接访问元素，时间复杂度O(1)且常数因子小
- 哈希表需要计算哈希值，可能发生冲突，虽然平均时间复杂度也是O(1)，但常数因子较大
内存布局：
- 数组在内存中是连续存储的，更有利于CPU缓存
- 哈希表的内部结构复杂，内存访问模式不规律，可能导致更多的缓存未命中
对象开销：
- 数组实现中使用基本类型int，没有额外的对象开销
- 哈希表中存储的是Integer对象，有额外的对象创建和垃圾回收开销
5.6 进一步优化可能性
5.6.1 内存优化
如果已知字符集更小（如只包含小写字母），可以使用更小的数组：
// 如果只包含小写字母a-z
int[] targetCount = new int[26];
int[] windowCount = new int[26];
// 转换字符为索引
for (char c : t.toCharArray()) {
int idx = c - 'a'; // 转换为0-25的索引
if (targetCount[idx] == 0) {
requiredChars++;
}
targetCount[idx]++;
}
// 类似地修改其他部分...
5.6.2 进一步的算法优化
- 跳过无关字符：
while (right < s.length()) {
char c = s.charAt(right);
// 如果当前字符不是目标字符，直接跳过
if (targetCount[c] == 0) {
right++;
continue;
}
// 其余逻辑...
}
- 提前检查起始位置：
// 检查第一个字符是否是目标字符之一
boolean found = false;
for (int i = 0; i < s.length(); i++) {
if (targetCount[s.charAt(i)] > 0) {
left = i;
found = true;
break;
}
}
if (!found) return ""; // 如果没有找到任何目标字符，直接返回空字符串
- 使用字符数组替代String.charAt：
char[] sChars = s.toCharArray();
for (int right = 0; right < sChars.length; right++) {
char c = sChars[right];
// 后续逻辑...
}
5.6.3 并行化处理
对于非常长的字符串，可以考虑将字符串分割成多个子段，并行处理：
- 将字符串s分割成多个重叠的子段
- 每个子段使用上述算法找到最小窗口
- 合并结果，取全局最小窗口
// 伪代码
List<String> segments = splitIntoOverlappingSegments(s, segmentSize, overlapSize);
List<MinWindowResult> results = segments.parallelStream()
.map(segment -> findMinWindow(segment, t))
.collect(Collectors.toList());
String globalMinWindow = findGlobalMinimum(results);
注意：这种优化只适用于非常长的字符串，对于普通长度的输入，额外的开销可能会抵消并行化带来的好处。
5.7 复杂度分析
时间复杂度：O(n)，其中 n 是字符串 s 的长度。每个字符最多被处理两次（添加到窗口和从窗口移除）。
空间复杂度：O(k)，其中 k 是字符集的大小。在这个实现中，k = 128（ASCII字符集大小）。相比于哈希表实现，空间复杂度的常数因子更小。
6. 优化技巧与常见错误详解
6.1 优化技巧全解析
6.1.1 使用数组替代哈希表
当字符集有限时（如ASCII字符或小写字母），使用数组代替哈希表可以显著提高效率。数组的优势在于：
- 直接索引访问：通过字符的ASCII值直接访问数组元素，避免哈希计算和冲突解决
- 内存连续性：数组的内存连续分布有利于CPU缓存命中率
- 减少对象开销：使用基本类型int替代Integer对象，减少装箱/拆箱和垃圾回收开销
代码实现：
// 假设字符集是ASCII
int[] charCount = new int[128];
// 增加计数
charCount[c]++;
// 减少计数
charCount[c]--;
// 判断字符是否存在
if (charCount[c] > 0) {
// 字符c存在
}
6.1.2 提前返回策略
在开始算法前检查一些基本条件，可以避免不必要的计算：
- 长度检查：如果源字符串长度小于目标字符串长度，直接返回空字符串
if (s.length() < t.length()) {
return "";
}
- 字符集检查：预先检查源字符串是否包含目标字符串中的所有字符
Set<Character> sChars = new HashSet<>();
for (char c : s.toCharArray()) {
sChars.add(c);
}
for (char c : t.toCharArray()) {
if (!sChars.contains(c)) {
return ""; // s不包含t中的某个字符，不可能有解
}
}
6.1.3 避免不必要的字符处理
在移动右指针时，可以跳过那些不在目标字符串中的字符：
while (right < s.length()) {
char c = s.charAt(right);
// 如果当前字符不是目标字符，跳过此字符
if (targetCount[c] == 0) {
right++;
continue;
}
// 处理目标字符
windowCount[c]++;
// ... 其他逻辑
right++;
}
注意：这种优化虽然可以减少一些不必要的操作，但会使代码更复杂，并可能导致边界条件处理错误。除非目标字符非常稀疏，否则这种优化的效果有限。
6.1.4 字符串预处理
对于重复调用的情况，可以预处理字符串，建立查找表：
// 预处理源字符串，建立每个字符的位置列表
Map<Character, List<Integer>> charPositions = new HashMap<>();
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
charPositions.computeIfAbsent(c, k -> new ArrayList<>()).add(i);
}
// 利用查找表快速定位字符
if (charPositions.containsKey(c)) {
List<Integer> positions = charPositions.get(c);
// 使用positions做进一步处理
}
6.1.5 优化内存使用
处理非常长的字符串时，可以采取以下措施优化内存使用：
- 使用字符数组代替String的charAt方法：
char[] sArray = s.toCharArray();
// 然后使用 sArray[i] 代替 s.charAt(i)
- 使用位图(Bitmap)替代整型数组（适用于小字符集）：
// 假设只关心是否出现，不关心出现次数
BitSet bitSet = new BitSet(26);
// 标记字符a-z的出现
bitSet.set(c - 'a');
// 检查字符是否出现
if (bitSet.get(c - 'a')) {
// 字符c出现过
}
- 优化循环结构，减少不必要的函数调用和对象创建
6.2 常见错误与解决方案
6.2.1 忽略字符重复出现的情况
错误：只考虑字符是否出现，而忽略出现次数。
// 错误代码
Set<Character> targetChars = new HashSet<>();
for (char c : t.toCharArray()) {
targetChars.add(c);
}
// 判断窗口是否满足条件
boolean windowContainsTarget = windowChars.containsAll(targetChars);
正确做法：必须考虑每个字符的出现次数。
// 正确代码
Map<Character, Integer> targetMap = new HashMap<>();
for (char c : t.toCharArray()) {
targetMap.put(c, targetMap.getOrDefault(c, 0) + 1);
}
// 判断窗口是否满足条件
boolean windowContainsTarget = true;
for (Map.Entry<Character, Integer> entry : targetMap.entrySet()) {
char c = entry.getKey();
int count = entry.getValue();
if (!windowMap.containsKey(c) || windowMap.get(c) < count) {
windowContainsTarget = false;
break;
}
}
6.2.2 错误的窗口收缩逻辑
错误：在窗口包含所有目标字符后立即停止扩张，但未找到最小窗口。
// 错误代码
while (right < s.length()) {
// ...扩大窗口...
if (windowContainsAllTargetChars()) {
// 找到一个满足条件的窗口，立即返回
return s.substring(left, right + 1);
}
right++;
}
正确做法：找到满足条件的窗口后，尝试通过移动左指针来最小化窗口。
// 正确代码
while (right < s.length()) {
// ...扩大窗口...
while (left <= right && windowContainsAllTargetChars()) {
// 更新最小窗口
if (right - left + 1 < minLen) {
minLen = right - left + 1;
minStart = left;
}
// 尝试缩小窗口
// ...移除左边界的字符...
left++;
}
right++;
}
6.2.3 错误的结果记录方式
错误：使用固定大小的变量记录结果，导致溢出或无法处理特殊情况。
// 错误代码
int minLen = 0; // 初始值设为0，可能导致无法区分未找到解的情况
正确做法：使用特殊值标记尚未找到解的情况。
// 正确代码
int minLen = Integer.MAX_VALUE; // 初始值设为最大整数，表示尚未找到解
// 最后检查是否找到解
return minLen == Integer.MAX_VALUE ? "" : s.substring(minStart, minStart + minLen);
6.2.4 边界条件处理不当
错误：未考虑各种边界情况，如空字符串、字符串长度为1等特殊情况。
正确做法：全面考虑边界情况。
// 正确代码
if (s == null || t == null || s.length() == 0 || t.length() == 0 || s.length() < t.length()) {
return "";
}
// 处理s等于t的特殊情况
if (s.equals(t)) {
return s;
}
// 处理t长度为1的特殊情况
if (t.length() == 1) {
int index = s.indexOf(t.charAt(0));
return index == -1 ? "" : t;
}
6.2.5 性能陷阱：频繁的字符串操作
错误：在循环中频繁创建子字符串或连接字符串。
// 错误代码
String result = "";
for (int i = 0; i < n; i++) {
result += s.charAt(i); // 每次迭代都创建新的字符串对象
}
正确做法：使用StringBuilder或直接记录索引。
// 正确代码 - 使用StringBuilder
StringBuilder sb = new StringBuilder();
for (int i = 0; i < n; i++) {
sb.append(s.charAt(i));
}
String result = sb.toString();
// 或者直接记录索引，最后一次性创建子字符串
int start = ...;
int end = ...;
String result = s.substring(start, end);
7. 实际应用场景详解
最小覆盖子串问题及其变体在实际开发中有广泛的应用。以下是一些具体的应用场景和示例。
7.1 文本搜索和信息检索
场景描述：在一段长文本中找到包含所有关键词的最小片段。
实际应用：搜索引擎的摘要生成、文档检索系统。
示例实现：
/**
* 在文档中查找包含所有关键词的最小片段
* @param document 文档内容
* @param keywords 关键词列表
* @return 最小片段
*/
public String findMinimumSnippet(String document, List<String> keywords) {
// 构建目标字符串（关键词拼接）
StringBuilder targetBuilder = new StringBuilder();
for (String keyword : keywords) {
targetBuilder.append(keyword);
}
String target = targetBuilder.toString();
// 使用最小覆盖子串算法查找
return minWindow(document, target);
}
改进方案：实际应用中，我们可能需要考虑词语而不是字符，这需要对算法进行修改：
public String findMinimumSnippetByWords(String document, List<String> keywords) {
// 分词处理
String[] words = document.split("\\s+");
// 构建目标词频表
Map<String, Integer> targetWordFreq = new HashMap<>();
for (String keyword : keywords) {
targetWordFreq.put(keyword, targetWordFreq.getOrDefault(keyword, 0) + 1);
}
// 应用滑动窗口算法
// ... (类似的算法，但处理单位是词而不是字符)
}
7.2 基因序列分析
场景描述：在DNA序列中找到包含特定碱基组合的最短子序列。
实际应用：基因组研究、病毒序列分析。
示例实现：
/**
* 在DNA序列中查找包含所有目标碱基组合的最短子序列
* @param dnaSequence DNA序列，如"ACGTACGTACGT"
* @param targetBases 目标碱基组合，如"AGT"
* @return 最短子序列
*/
public String findMinimumDNASequence(String dnaSequence, String targetBases) {
return minWindow(dnaSequence, targetBases);
}
实际案例：
在COVID-19病毒研究中，科学家需要在病毒基因组中找到包含特定碱基序列的区域，这些区域可能与病毒的特性（如传染性、致病性）相关。
7.3 网络流量分析
场景描述：在网络数据包流中找到包含所有必要信息的最小数据段。
实际应用：网络监控、入侵检测系统。
示例实现：
/**
* 在网络数据流中查找包含所有必要标记的最小数据段
* @param dataStream 数据流内容
* @param requiredMarkers 必要标记列表
* @return 最小数据段的起始位置和长度
*/
public int[] findMinimumDataSegment(byte[] dataStream, byte[] requiredMarkers) {
// 转换为字符串处理（简化示例）
String dataStr = new String(dataStream);
String markersStr = new String(requiredMarkers);
String result = minWindow(dataStr, markersStr);
if (result.isEmpty()) {
return new int[]{-1, 0}; // 未找到
} else {
int start = dataStr.indexOf(result);
return new int[]{start, result.length()};
}
}
7.4 图像处理中的区域搜索
场景描述：在二维图像矩阵中找到包含所有目标像素的最小矩形区域。
实际应用：对象检测、图像分割。
算法扩展：
/**
* 在图像矩阵中查找包含所有目标像素的最小矩形区域
* @param image 二维图像矩阵
* @param targetPixels 目标像素值列表
* @return 最小矩形区域的坐标 [top, left, bottom, right]
*/
public int[] findMinimumRectangle(int[][] image, int[] targetPixels) {
// 这是一个2D版本的最小覆盖子串问题
// 可以采用滑动窗口的思想，但需要扩展到二维
// ...实现略...
}
7.5 推荐系统中的内容聚合
场景描述：在用户内容流中找到包含用户所有兴趣关键词的最小内容集合。
实际应用：个性化推荐、内容聚合。
示例实现：
/**
* 在内容列表中查找包含用户所有兴趣关键词的最小内容集合
* @param contents 内容列表
* @param userInterests 用户兴趣关键词列表
* @return 最小内容集合的索引范围
*/
public int[] findMinimumContentBundle(List<String> contents, List<String> userInterests) {
// 将内容列表拼接成字符串，用特殊分隔符隔开
StringBuilder sb = new StringBuilder();
for (String content : contents) {
sb.append(content).append("###"); // 使用特殊分隔符
}
String contentStr = sb.toString();
// 将用户兴趣关键词拼接成目标字符串
StringBuilder targetSb = new StringBuilder();
for (String interest : userInterests) {
targetSb.append(interest);
}
String targetStr = targetSb.toString();
// 应用最小覆盖子串算法
// ... (需要特殊处理分隔符)
}
8. 进阶问题及变体
除了基本的最小覆盖子串问题，还有许多相关的变体和进阶问题。掌握了滑动窗口算法后，可以尝试解决以下问题：
8.1 找到字符串中所有字母异位词 (LeetCode 438)
题目描述：给定一个字符串 s 和一个非空字符串 p，找到 s 中所有是 p 的字母异位词的子串，返回这些子串的起始索引。
关键思路：
- 字母异位词意味着两个字符串包含相同的字符和相同的字符频率
- 可以使用固定大小的滑动窗口（长度等于p的长度）
- 使用数组或哈希表记录窗口中各字符的出现频率，与目标频率比较
代码实现：
public List<Integer> findAnagrams(String s, String p) {
List<Integer> result = new ArrayList<>();
if (s == null || p == null || s.length() < p.length()) {
return result;
}
// 记录目标字符串和当前窗口中各字符的出现频率
int[] targetCount = new int[26]; // 假设只包含小写字母
int[] windowCount = new int[26];
// 统计目标字符串中各字符的出现频率
for (char c : p.toCharArray()) {
targetCount[c - 'a']++;
}
// 初始窗口
int windowSize = p.length();
for (int i = 0; i < windowSize && i < s.length(); i++) {
windowCount[s.charAt(i) - 'a']++;
}
// 检查初始窗口是否是异位词
if (Arrays.equals(targetCount, windowCount)) {
result.add(0);
}
// 滑动窗口
for (int i = windowSize; i < s.length(); i++) {
// 移出窗口左侧的字符
windowCount[s.charAt(i - windowSize) - 'a']--;
// 移入窗口右侧的字符
windowCount[s.charAt(i) - 'a']++;
// 检查当前窗口是否是异位词
if (Arrays.equals(targetCount, windowCount)) {
result.add(i - windowSize + 1);
}
}
return result;
}
8.2 字符串的排列 (LeetCode 567)
题目描述：给定两个字符串 s1 和 s2，判断 s2 是否包含 s1 的排列（即 s1 的某个字母异位词是 s2 的子串）。
示例：
- 输入: s1 = “ab”, s2 = “eidbaooo”
- 输出: true
- 解释: s2 包含 s1 的排列"ba"
代码实现：
public boolean checkInclusion(String s1, String s2) {
if (s1 == null || s2 == null || s1.length() > s2.length()) {
return false;
}
// 记录目标字符串和当前窗口中各字符的出现频率
int[] targetCount = new int[26]; // 假设只包含小写字母
int[] windowCount = new int[26];
// 统计目标字符串中各字符的出现频率
for (char c : s1.toCharArray()) {
targetCount[c - 'a']++;
}
// 初始窗口
int windowSize = s1.length();
for (int i = 0; i < windowSize && i < s2.length(); i++) {
windowCount[s2.charAt(i) - 'a']++;
}
// 检查初始窗口是否是排列
if (Arrays.equals(targetCount, windowCount)) {
return true;
}
// 滑动窗口
for (int i = windowSize; i < s2.length(); i++) {
// 移出窗口左侧的字符
windowCount[s2.charAt(i - windowSize) - 'a']--;
// 移入窗口右侧的字符
windowCount[s2.charAt(i) - 'a']++;
// 检查当前窗口是否是排列
if (Arrays.equals(targetCount, windowCount)) {
return true;
}
}
return false;
}
8.3 无重复字符的最长子串 (LeetCode 3)
题目描述：给定一个字符串，找出其中不含重复字符的最长子串的长度。
示例：
- 输入: “abcabcbb”
- 输出: 3
- 解释: 最长子串是 “abc”，长度为 3
代码实现：
public int lengthOfLongestSubstring(String s) {
if (s == null || s.length() == 0) {
return 0;
}
// 记录字符最后出现的位置
Map<Character, Integer> lastPosition = new HashMap<>();
int maxLength = 0;
int start = 0; // 当前无重复子串的起始位置
for (int end = 0; end < s.length(); end++) {
char c = s.charAt(end);
// 如果字符已经在当前窗口中出现过，更新窗口起始位置
if (lastPosition.containsKey(c) && lastPosition.get(c) >= start) {
start = lastPosition.get(c) + 1;
}
// 更新最大长度
maxLength = Math.max(maxLength, end - start + 1);
// 更新字符最后出现的位置
lastPosition.put(c, end);
}
return maxLength;
}
8.4 至多包含两个不同字符的最长子串 (LeetCode 159)
题目描述：给定一个字符串，找出其中最多包含两个不同字符的最长子串的长度。
示例：
- 输入: “eceba”
- 输出: 3
- 解释: 最长子串是 “ece”，长度为 3
代码实现：
public int lengthOfLongestSubstringTwoDistinct(String s) {
if (s == null || s.length() == 0) {
return 0;
}
Map<Character, Integer> charCount = new HashMap<>();
int maxLength = 0;
int left = 0;
for (int right = 0; right < s.length(); right++) {
char c = s.charAt(right);
// 更新字符计数
charCount.put(c, charCount.getOrDefault(c, 0) + 1);
// 当窗口中不同字符的数量大于2时，收缩窗口
while (charCount.size() > 2) {
char leftChar = s.charAt(left);
charCount.put(leftChar, charCount.get(leftChar) - 1);
if (charCount.get(leftChar) == 0) {
charCount.remove(leftChar);
}
left++;
}
// 更新最大长度
maxLength = Math.max(maxLength, right - left + 1);
}
return maxLength;
}
8.5 至多包含K个不同字符的最长子串 (LeetCode 340)
题目描述：给定一个字符串和一个整数 k，找出其中最多包含 k 个不同字符的最长子串的长度。
示例：
- 输入: s = “eceba”, k = 2
- 输出: 3
- 解释: 最长子串是 “ece”，长度为 3
代码实现：
public int lengthOfLongestSubstringKDistinct(String s, int k) {
if (s == null || s.length() == 0 || k == 0) {
return 0;
}
Map<Character, Integer> charCount = new HashMap<>();
int maxLength = 0;
int left = 0;
for (int right = 0; right < s.length(); right++) {
char c = s.charAt(right);
// 更新字符计数
charCount.put(c, charCount.getOrDefault(c, 0) + 1);
// 当窗口中不同字符的数量大于k时，收缩窗口
while (charCount.size() > k) {
char leftChar = s.charAt(left);
charCount.put(leftChar, charCount.get(leftChar) - 1);
if (charCount.get(leftChar) == 0) {
charCount.remove(leftChar);
}
left++;
}
// 更新最大长度
maxLength = Math.max(maxLength, right - left + 1);
}
return maxLength;
}
8.6 水果成篮 (LeetCode 904)
题目描述：在一排树中，每棵树上都有一种水果。你可以从左到右拿水果，但有两个限制条件：1) 你最多只能拿两种不同类型的水果；2) 一旦你不再拿某种类型的水果，你就不能再拿同一类型的水果。请找出最多能拿到的水果数量。
示例：
- 输入: [1,2,1,2,3]
- 输出: 4
- 解释: 可以拿到的水果为 [2,1,2,1]，无法拿到 3 类水果
代码实现：
public int totalFruit(int[] tree) {
if (tree == null || tree.length == 0) {
return 0;
}
Map<Integer, Integer> fruitCount = new HashMap<>();
int maxFruits = 0;
int left = 0;
for (int right = 0; right < tree.length; right++) {
int fruit = tree[right];
// 添加新水果
fruitCount.put(fruit, fruitCount.getOrDefault(fruit, 0) + 1);
// 当篮子中的水果种类超过2时，移除最早的那种水果
while (fruitCount.size() > 2) {
int leftFruit = tree[left];
fruitCount.put(leftFruit, fruitCount.get(leftFruit) - 1);
if (fruitCount.get(leftFruit) == 0) {
fruitCount.remove(leftFruit);
}
left++;
}
// 更新最大水果数量
maxFruits = Math.max(maxFruits, right - left + 1);
}
return maxFruits;
}
9. 面试技巧与总结
9.1 解题步骤梳理
面对最小覆盖子串及其变体问题，可以遵循以下步骤：
识别问题类型：
- 判断是否是子串/子数组问题
- 判断是否需要满足某种特定条件
- 判断是否需要最优解（最长/最短）
选择合适的算法：
- 如果是子串/子数组问题，考虑使用滑动窗口
- 如果需要查找所有可能解，考虑使用回溯或动态规划
- 如果是实时处理或数据流问题，考虑使用滑动窗口+哈希表
确定窗口状态和条件：
- 窗口的扩张条件：什么情况下需要扩大窗口？
- 窗口的收缩条件：什么情况下需要缩小窗口？
- 窗口状态的维护：如何高效判断窗口是否满足条件？
考虑边界条件：
- 空字符串处理
- 单字符字符串处理
- 无解情况处理
优化算法：
- 空间优化：使用数组代替哈希表（如果可能）
- 时间优化：减少不必要的操作，如判断、函数调用
- 提前返回：识别无解情况，尽早返回
9.2 编码时的注意事项
变量命名：使用有意义的变量名，如
targetCount、windowCount、minLen等。代码注释：添加清晰的注释，特别是对关键逻辑和边界条件的处理。
模块化：将复杂逻辑拆分为辅助函数，提高代码可读性。
private boolean windowContainsTarget(int[] windowCount, int[] targetCount) {
// 检查窗口是否包含所有目标字符
}
- 避免重复计算：使用变量存储中间结果，避免重复计算。
// 记录已满足条件的字符数量，避免每次都遍历检查
int formed = 0;
- 健壮性处理：处理各种边界条件和异常情况。
9.3 测试用例设计
设计全面的测试用例，包括：
基本情况：
- 正常输入，有唯一解
- 正常输入，有多个解（应返回最优解）
边界情况：
- 空字符串
- 单字符字符串
- 源字符串等于目标字符串
- 源字符串长度等于目标字符串长度
特殊情况：
- 目标字符串中有重复字符
- 所有字符都相同
- 字符集很大或很小
- 无解情况
性能测试：
- 非常长的字符串
- 目标字符非常稀疏或非常密集
9.4 滑动窗口算法总结
核心思想：
- 使用两个指针表示窗口的左右边界
- 动态调整窗口，寻找满足条件的最优解
适用场景：
- 字符串/数组的连续子序列问题
- 需要满足某种条件的最长/最短子序列
- 有限范围内的计数或频率问题
优点：
- 时间复杂度优秀，通常为O(n)
- 空间复杂度通常较低
- 算法思路直观，易于理解
变种：
- 固定长度的滑动窗口
- 可变长度的滑动窗口
- 多指针滑动窗口
常见应用：
- 字符串匹配
- 连续子数组的最大/最小和
- K个不同元素的最长子数组
- 字母异位词查找
掌握滑动窗口技术，能够帮助你解决各种字符串和数组的子序列问题。通过理解本文中的最小覆盖子串问题及其变体，你将能够应对大多数此类问题。