LeetCode 76 - 最小覆盖子串（Minimum Window Substring）

算法刷题>LeetCode>面试经典150
14k words

LeetCode 76 - 最小覆盖子串

问题描述

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。

注意：

  • 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
  • 如果 s 中存在这样的子串，我们保证它是唯一的答案。

示例

示例 1：

1
2
3
输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"
解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。

示例 2：

1
2
3
输入：s = "a", t = "a"
输出："a"
解释：整个字符串 s 是最小覆盖子串。

示例 3：

1
2
3
4
输入: s = "a", t = "aa"
输出: ""
解释: t 中两个字符 'a' 均应包含在 s 的子串中，
因此没有符合条件的子字符串，返回空字符串。

约束条件

  • m == s.length
  • n == t.length
  • 1 <= m, n <= 10^5
  • s 和 t 由英文字母组成

进阶： 你能设计一个在 $O(m+n)$ 时间内解决此问题的算法吗？

解题思路

这是一道经典的滑动窗口问题，但比普通滑动窗口更复杂，因为需要：

  1. 确保窗口包含 t 的所有字符
  2. 保证每个字符的数量不少于 t 中的数量
  3. 找到满足条件的最短子串

核心思想

使用滑动窗口 + 哈希数组的方法：

  1. 统计 t 的字符需求：使用 need 数组记录 t 中每个字符的需求量
  2. 维护滑动窗口：使用 window 数组记录窗口中每个字符的数量
  3. 跟踪满足条件：使用 valid 变量记录当前窗口中满足需求的字符种类数
  4. 扩展和收缩窗口：
    • 右指针扩展窗口，添加字符
    • 当窗口满足所有需求时，收缩左边界寻找更短子串
  5. 更新最小长度：记录满足条件的最短子串起始位置和长度

算法步骤详解

步骤 1：初始化数据结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 字符需求数组（ASCII 码范围 0-127）
int[] need = new int[128];  // 记录 t 中各字符的需求量
int[] window = new int[128]; // 记录窗口中各字符的数量

// 统计 t 中各字符的需求量
for(char c : t.toCharArray()){
    need[c] ++;
}

// 计算需要满足的不同字符种类数
int required = 0;
for(int count : need){
    if(count > 0){
        required ++;
    }
}

关键点：

  • 使用数组而非 HashMap，因为字符范围有限（ASCII 0-127），数组访问更快
  • required 表示 t 中有多少种不同的字符，用于判断窗口是否满足条件

步骤 2：滑动窗口遍历

1
2
3
4
5
6
7
8
9
int left = 0, right = 0;        // 滑动窗口左右指针
int valid = 0;                  // 当前窗口满足需求的字符种类数
int start = 0, minLen = Integer.MAX_VALUE; // 记录最小覆盖子串信息

while(right < s.length()){
    // 扩展窗口
    // 收缩窗口（当满足条件时）
    // 更新最小长度
}

步骤 3：扩展右边界

1
2
3
4
5
6
7
8
9
10
11
char c = s.charAt(right);
right ++;

// 更新窗口数据（仅处理 t 中存在的字符）
if(need[c] > 0){
    window[c] ++;
    // 当窗口中该字符数量达到需求时，valid + 1
    if(window[c] == need[c]){
        valid ++;
    }
}

逻辑说明：

  • 只有当 need[c] > 0 时才处理，即该字符在 t 中出现过
  • window[c] == need[c] 表示该字符在窗口中的数量恰好满足需求
  • valid++ 表示又多了一种字符满足需求

步骤 4：收缩左边界

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 当窗口满足所有需求时，尝试收缩左边界
while(valid == required){
    // 更新最小覆盖子串信息
    if(right - left < minLen){
        start = left;
        minLen = right - left; // right 已经指向下一位
    }

    char d = s.charAt(left);
    left ++;

    // 更新窗口数据（仅处理 t 中存在的字符）
    if(need[d] > 0){
        // 当移出字符导致数量不足时，valid - 1
        if(window[d] == need[d]){
            valid --;
        }
        window[d] --;
    }
}

关键点：

  • valid == required 表示窗口中所有字符类型都满足需求
  • right - left 计算窗口长度（因为 right 已经自增，指向下一个位置）
  • 当 window[d] == need[d] 时，说明移除该字符后会导致不满足需求，需要 valid--

执行过程示例

以 s = "ADOBECODEBANC", t = "ABC" 为例，详细跟踪每一步执行过程：

初始化阶段

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// 输入：s = "ADOBECODEBANC", t = "ABC"

// 步骤 1：边界检查
s.length() = 13, t.length() = 3 → 13 >= 3，继续执行

// 步骤 2：初始化数组
int[] need = new int[128];  // 所有元素初始化为 0
int[] window = new int[128]; // 所有元素初始化为 0

// 步骤 3：统计 t 中各字符的需求量
遍历 t = "ABC":
  - need['A'] = 1
  - need['B'] = 1
  - need['C'] = 1
  - 其他字符 need[ch] = 0

// 步骤 4：计算需要满足的字符种类数
遍历 need 数组，统计 count > 0 的个数：
  - required = 3 (A, B, C 三种字符)

// 步骤 5：初始化滑动窗口变量
int left = 0, right = 0;
int valid = 0;
int start = 0, minLen = Integer.MAX_VALUE;

初始状态总结：

  • need 数组：只有 ‘A’, ‘B’, ‘C’ 的位置为 1，其他为 0
  • window 数组：所有元素为 0
  • required = 3：需要满足 3 种字符
  • valid = 0：当前满足的字符种类数为 0
  • 窗口：[left=0, right=0)，当前为空窗口

滑动窗口遍历过程

迭代 1：right = 0, c = ‘A’

1
2
3
4
5
6
7
8
9
10
11
12
13
读取字符：c = s.charAt(0) = 'A'
right++ → right = 1

判断：need['A'] = 1 > 0，需要处理
  执行：window['A']++ → window['A'] = 1
  判断：window['A'] == need['A'] (1 == 1) ✓
  执行：valid++ → valid = 1

当前状态：
  - 窗口内容：s[0..0] = "A"
  - window['A'] = 1, window['B'] = 0, window['C'] = 0
  - valid = 1, required = 3
  - valid < required，不满足条件，继续扩展

迭代 2：right = 1, c = ‘D’

1
2
3
4
5
6
7
8
9
10
11
读取字符：c = s.charAt(1) = 'D'
right++ → right = 2

判断：need['D'] = 0，不在 t 中，跳过处理
  不更新 window，不更新 valid

当前状态：
  - 窗口内容：s[0..1] = "AD"
  - window['A'] = 1, window['B'] = 0, window['C'] = 0
  - valid = 1, required = 3
  - valid < required，不满足条件，继续扩展

迭代 3：right = 2, c = ‘O’

1
2
3
4
5
6
7
8
9
10
读取字符：c = s.charAt(2) = 'O'
right++ → right = 3

判断：need['O'] = 0，不在 t 中，跳过处理

当前状态：
  - 窗口内容：s[0..2] = "ADO"
  - window['A'] = 1, window['B'] = 0, window['C'] = 0
  - valid = 1, required = 3
  - valid < required，继续扩展

迭代 4：right = 3, c = ‘B’

1
2
3
4
5
6
7
8
9
10
11
12
13
读取字符：c = s.charAt(3) = 'B'
right++ → right = 4

判断：need['B'] = 1 > 0，需要处理
  执行：window['B']++ → window['B'] = 1
  判断：window['B'] == need['B'] (1 == 1) ✓
  执行：valid++ → valid = 2

当前状态：
  - 窗口内容：s[0..3] = "ADOB"
  - window['A'] = 1, window['B'] = 1, window['C'] = 0
  - valid = 2, required = 3
  - valid < required，不满足条件，继续扩展

迭代 5：right = 4, c = ‘E’

1
2
3
4
5
6
7
8
9
10
读取字符：c = s.charAt(4) = 'E'
right++ → right = 5

判断：need['E'] = 0，不在 t 中，跳过处理

当前状态：
  - 窗口内容：s[0..4] = "ADOBE"
  - window['A'] = 1, window['B'] = 1, window['C'] = 0
  - valid = 2, required = 3
  - valid < required，继续扩展

迭代 6：right = 5, c = ‘C’（关键步骤）

1
2
3
4
5
6
7
8
9
10
11
12
13
读取字符：c = s.charAt(5) = 'C'
right++ → right = 6

判断：need['C'] = 1 > 0，需要处理
  执行：window['C']++ → window['C'] = 1
  判断：window['C'] == need['C'] (1 == 1) ✓
  执行：valid++ → valid = 3

当前状态：
  - 窗口内容：s[0..5] = "ADOBEC"
  - window['A'] = 1, window['B'] = 1, window['C'] = 1
  - valid = 3, required = 3
  - valid == required ✓ 满足条件！进入收缩阶段

收缩窗口（第一次满足条件）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
while(valid == required) {  // valid = 3 == required = 3，进入循环
  // 更新最小覆盖子串信息
  if(right - left < minLen) {
    // right = 6, left = 0
    // 6 - 0 = 6 < Integer.MAX_VALUE
    start = 0;
    minLen = 6;  // 第一个满足条件的子串长度：6
  }

  // 收缩左边界
  char d = s.charAt(0) = 'A';
  left++ → left = 1;

  // 更新窗口数据
  if(need['A'] > 0) {  // need['A'] = 1 > 0
    // 判断移出前是否恰好满足需求
    if(window['A'] == need['A']) {  // 1 == 1 ✓
      valid--;  // 移出后不再满足，valid = 2
    }
    window['A']--;  // window['A'] = 0
  }
  
  // 收缩后状态：
  //   - 窗口内容：s[1..5] = "DOBEC"
  //   - window['A'] = 0, window['B'] = 1, window['C'] = 1
  //   - valid = 2, required = 3
  //   - valid < required，退出 while 循环
}

迭代 7：right = 6, c = ‘O’

1
2
3
4
5
6
7
8
9
10
读取字符：c = s.charAt(6) = 'O'
right++ → right = 7

判断：need['O'] = 0，不在 t 中，跳过处理

当前状态：
  - 窗口内容：s[1..6] = "DOBECO"
  - window['A'] = 0, window['B'] = 1, window['C'] = 1
  - valid = 2, required = 3
  - valid < required，不满足条件，继续扩展

迭代 8：right = 7, c = ‘D’

1
2
3
4
5
6
7
8
9
10
读取字符：c = s.charAt(7) = 'D'
right++ → right = 8

判断：need['D'] = 0，不在 t 中，跳过处理

当前状态：
  - 窗口内容：s[1..7] = "DOBECOD"
  - window['A'] = 0, window['B'] = 1, window['C'] = 1
  - valid = 2, required = 3
  - valid < required，继续扩展

迭代 9：right = 8, c = ‘E’

1
2
3
4
5
6
7
8
9
10
读取字符：c = s.charAt(8) = 'E'
right++ → right = 9

判断：need['E'] = 0，不在 t 中，跳过处理

当前状态：
  - 窗口内容：s[1..8] = "DOBECODE"
  - window['A'] = 0, window['B'] = 1, window['C'] = 1
  - valid = 2, required = 3
  - valid < required，继续扩展

迭代 10：right = 9, c = ‘B’（重要步骤）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
读取字符：c = s.charAt(9) = 'B'
right++ → right = 10

判断：need['B'] = 1 > 0，需要处理
  执行：window['B']++ → window['B'] = 2
  判断：window['B'] == need['B'] (2 == 1) ✗
  注意：此时 window['B'] > need['B']，不增加 valid
  valid 保持不变 = 2

当前状态：
  - 窗口内容：s[1..9] = "DOBECODEB"
  - window['A'] = 0, window['B'] = 2, window['C'] = 1
  - valid = 2, required = 3
  - valid < required，继续扩展（缺少 'A'）

迭代 11：right = 10, c = ‘A’（关键步骤）

1
2
3
4
5
6
7
8
9
10
11
12
13
读取字符：c = s.charAt(10) = 'A'
right++ → right = 11

判断：need['A'] = 1 > 0，需要处理
  执行：window['A']++ → window['A'] = 1
  判断：window['A'] == need['A'] (1 == 1) ✓
  执行：valid++ → valid = 3

当前状态：
  - 窗口内容：s[1..10] = "DOBECODEBA"
  - window['A'] = 1, window['B'] = 2, window['C'] = 1
  - valid = 3, required = 3
  - valid == required ✓ 满足条件！进入收缩阶段

收缩窗口（第二次满足条件，寻找更短子串）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
while(valid == required) {  // valid = 3 == required = 3
  // 更新最小覆盖子串信息
  if(right - left < minLen) {
    // right = 11, left = 1
    // 11 - 1 = 10 >= 6，不更新（当前子串更长）
    // start = 0, minLen = 6（保持不变）
  }

  // 收缩左边界
  char d = s.charAt(1) = 'D';
  left++ → left = 2;

  // need['D'] = 0，不处理
  // 收缩后 valid 仍为 3，继续循环
}

// 第二次收缩
while(valid == required) {  // valid = 3 == required = 3，继续循环
  if(right - left < minLen) {
    // right = 11, left = 2
    // 11 - 2 = 9 >= 6，不更新
  }

  char d = s.charAt(2) = 'O';
  left++ → left = 3;
  // need['O'] = 0，不处理
}

// ... 继续收缩直到遇到关键字符 ...

迭代 12：right = 11, c = ‘N’

1
2
3
4
5
6
7
8
9
10
读取字符：c = s.charAt(11) = 'N'
right++ → right = 12

判断：need['N'] = 0，不在 t 中，跳过处理

当前状态：
  - 窗口内容：s[1..11] = "DOBECODEBAN"
  - window['A'] = 1, window['B'] = 2, window['C'] = 1
  - valid = 3, required = 3
  - valid == required ✓ 继续收缩

迭代 13：right = 12, c = ‘C’（最后一次扩展）

1
2
3
4
5
6
7
8
9
10
11
12
13
读取字符：c = s.charAt(12) = 'C'
right++ → right = 13

判断：need['C'] = 1 > 0，需要处理
  执行：window['C']++ → window['C'] = 2
  判断：window['C'] == need['C'] (2 == 1) ✗
  valid 保持不变 = 3

当前状态：
  - 窗口内容：s[1..12] = "DOBECODEBANC"
  - window['A'] = 1, window['B'] = 2, window['C'] = 2
  - valid = 3, required = 3
  - valid == required ✓ 满足条件！进入收缩阶段

关键收缩过程（找到最小子串）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
// 持续收缩，直到找到最短满足条件的子串
// 当前窗口：s[1..12] = "DOBECODEBANC"

// 收缩 'D', 'O', 'B', 'E', 'C', 'O', 'D', 'E'
// 这些字符的移除不影响 valid（因为它们不在 t 中，或者数量仍大于需求）

// 直到 left = 9，窗口变为 s[9..12] = "BANC"
while(valid == required) {
  if(right - left < minLen) {
    // right = 13, left = 9
    // 13 - 9 = 4 < 6 ✓ 找到更短的子串！
    start = 9;
    minLen = 4;  // 更新为最短长度：4
  }

  char d = s.charAt(9) = 'B';
  left++ → left = 10;

  if(need['B'] > 0) {
    // window['B'] = 2, need['B'] = 1
    // window['B'] > need['B']，移出一个 'B' 后仍满足需求
    // 不减少 valid
    window['B']--;  // window['B'] = 1
  }
  
  // 收缩后仍满足条件，继续循环
}

// 继续收缩
while(valid == required) {
  if(right - left < minLen) {
    // right = 13, left = 10
    // 13 - 10 = 3 < 4 ✓ 找到更短的子串！
    start = 10;
    minLen = 3;
  }

  char d = s.charAt(10) = 'A';
  left++ → left = 11;

  if(need['A'] > 0) {
    if(window['A'] == need['A']) {  // 1 == 1 ✓
      valid--;  // valid = 2，不再满足条件
    }
    window['A']--;  // window['A'] = 0
  }
  
  // valid = 2 < required = 3，退出 while 循环
}

最终结果

1
2
3
4
5
6
7
8
9
// 当 right = 13 时，退出主循环（right >= s.length()）
// 此时已经找到满足条件的最短子串

// 最终结果：
start = 9;
minLen = 4;

// 返回结果
return s.substring(9, 9 + 4) = "BANC"

最终答案验证：

  • 窗口：s[9..12] = "BANC"
  • 包含的字符：’B’, ‘A’, ‘N’, ‘C’
  • t 中的字符：’A’, ‘B’, ‘C’ ✓ 全部包含
  • ‘A’ 出现 1 次，需求 1 次 ✓
  • ‘B’ 出现 1 次，需求 1 次 ✓
  • ‘C’ 出现 1 次，需求 1 次 ✓
  • 长度：4（最短）

最终结果：

  • start = 9
  • minLen = 4
  • 返回 s.substring(9, 9 + 4) = "BANC" ✓

执行过程总结表

迭代 right left 窗口内容 window状态 valid 操作 更新minLen
初始 0 0 “” A:0,B:0,C:0 0 - MAX
1 1 0 “A” A:1,B:0,C:0 1 扩展 -
2 2 0 “AD” A:1,B:0,C:0 1 扩展 -
3 3 0 “ADO” A:1,B:0,C:0 1 扩展 -
4 4 0 “ADOB” A:1,B:1,C:0 2 扩展 -
5 5 0 “ADOBE” A:1,B:1,C:0 2 扩展 -
6 6 0 “ADOBEC” A:1,B:1,C:1 3 扩展 6
6收缩 6 1 “DOBEC” A:0,B:1,C:1 2 收缩 -
7-9 7-9 1 “DOBEC…” A:0,B:1,C:1 2 扩展 -
10 10 1 “DOBECODEBA” A:1,B:2,C:1 3 扩展 -
10收缩 10 9 “BANC” A:1,B:1,C:1 3 收缩 4 ✓
11-13 13 9+ “BANC” - - 最终 -

最终答案："BANC"（从索引 9 开始，长度为 4）

实现细节

边界条件处理

1
2
3
4
// 边界条件处理：若 s 比 t 短或 t 为空，则直接返回空字符串
if(s == null || t == null || s.length() < t.length()){
    return "";
}

为什么需要这个判断：

  • 如果 s.length() < t.length()，s 中不可能包含 t 的所有字符
  • 提前返回可以避免不必要的计算

哈希数组优化

使用数组而非 HashMap 的优势：

方面 数组 HashMap
访问速度 O(1) 直接索引 O(1) 但需要哈希计算
内存占用 固定 128 个整数 动态分配，只存储出现字符
缓存友好 连续内存，缓存命中率高 散列存储，缓存效果差
实现简洁 代码更简洁 需要处理键值对

对于字符范围已知的情况（ASCII 0-127），数组是更好的选择。

valid 变量的作用

valid 变量是关键优化，它记录满足需求的字符种类数：

  • 当 window[c] == need[c] 时，该字符满足需求，valid++
  • 当 window[d] == need[d] 且要移除 d 时，该字符将不再满足需求，valid--
  • 当 valid == required 时，窗口包含 t 的所有字符且数量满足要求

为什么需要 valid：

  • 如果不使用 valid，每次判断都需要遍历 need 数组检查所有字符是否满足需求，时间复杂度会增加到 $O(n \times m)$
  • 使用 valid 可以将判断优化到 $O(1)$

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
class Solution {
    public String minWindow(String s, String t) {
        // 边界条件处理：若 s 比 t 短或 t 为空，则直接返回空字符串
        if(s == null || t == null || s.length() < t.length()){
            return "";
        }

        // 初始化字符所需数组（ASCII 码范围为 0-127）
        int[] need = new int[128];
        int[] window = new int[128];

        // 统计 t 中各字符的需求量
        for(char c : t.toCharArray()){
            need[c] ++;
        }

        // 需要满足的不同字符种类数
        int required = 0;
        for(int count : need){
            if(count > 0){
                required ++;
            }
        }

        int left = 0, right = 0; // 滑动窗口左右指针
        int valid = 0; // 当前窗口满足需求的字符种类数
        int start = 0, minLen = Integer.MAX_VALUE; // 记录最小覆盖子串信息

        // 开始滑动窗口遍历
        while(right < s.length()){
            char c = s.charAt(right);
            right ++;

            // 更新窗口数据（仅处理 t 中存在的字符）
            if(need[c] > 0){
                window[c] ++;
                // 当窗口中该字符数量达到需求时，valid + 1
                if(window[c] == need[c]){
                    valid ++ ;
                }
            }

            // 当窗口满足所有需求时，尝试收缩左边界
            while(valid == required){
                // 更新最小覆盖子串信息
                if(right - left < minLen){
                    start = left;
                    minLen = right - left; // right 已经指向下一位
                }

                char d = s.charAt(left);
                left ++;

                // 更新窗口数据（仅处理 t 中存在的字符）
                if(need[d] > 0){
                    // 当移出字符导致数量不足时，valid - 1
                    if(window[d] == need[d]){
                        valid -- ;
                    }
                    window [d] -- ;
                }
            }
        }

        // 返回结果（若未找到则返回空字符串）
        return minLen == Integer.MAX_VALUE ? "" : s.substring(start , start + minLen);
    }
}

代码关键点解析

  1. 字符数组索引：

    1
    2
    int[] need = new int[128];
    need[c] ++;  // c 会被自动转换为 ASCII 码值作为索引

    Java 中 char 可以直接转换为 int，范围 0-127 的字符可以直接作为数组索引。

  2. right 指针的处理：

    1
    2
    3
    4
    char c = s.charAt(right);
    right ++;
    // ...
    minLen = right - left; // right 已经指向下一位

    在更新 minLen 时，right 已经自增，指向下一个位置，所以窗口长度是 right - left 而不是 right - left + 1。

  3. valid 的判断时机：

    1
    2
    3
    if(window[c] == need[c]){
        valid ++;
    }

    只有当数量恰好相等时才增加 valid，如果 window[c] > need[c] 不会再增加 valid。

  4. 收缩窗口的条件：

    1
    while(valid == required)

    使用 while 而非 if，因为收缩一个字符后可能仍然满足条件，需要继续收缩寻找更短子串。

复杂度分析

时间复杂度

$O(m + n)$，其中 $m$ 是字符串 s 的长度，$n$ 是字符串 t 的长度。

分析：

  • 初始化 need 数组：$O(n)$
  • 计算 required：$O(128) = O(1)$
  • 滑动窗口遍历：
    • 每个元素最多被右指针访问一次：$O(m)$
    • 每个元素最多被左指针访问一次：$O(m)$
    • 总时间复杂度：$O(m)$

因此总时间复杂度为 $O(m + n)$。

空间复杂度

$O(1)$。

分析：

  • need 数组：固定大小 128，$O(1)$
  • window 数组：固定大小 128，$O(1)$
  • 其他变量：常数空间，$O(1)$

虽然使用了两个大小为 128 的数组，但这是固定大小，不随输入规模增长，因此空间复杂度为 $O(1)$。

方法比较

方面 哈希数组方法 HashMap 方法
时间复杂度 $O(m+n)$ $O(m+n)$
空间复杂度 $O(1)$ $O(1)$
代码简洁度 ★★★★☆ ★★★☆☆
执行效率 更快（直接索引） 较慢（哈希运算）
内存占用 固定 256 个整数 动态分配
适用场景 字符范围已知 通用场景
推荐度 ★★★★★ ★★★☆☆

关键收获

算法要点

  1. 滑动窗口的扩展与收缩：

    • 右指针扩展窗口，添加字符
    • 左指针收缩窗口，移除字符
    • 收缩时寻找满足条件的最短子串

  2. valid 变量的优化：

    • 使用 valid 变量跟踪满足需求的字符种类数
    • 避免每次都检查所有字符是否满足需求
    • 将判断时间复杂度从 $O(n)$ 优化到 $O(1)$

  3. 哈希数组的选择：

    • 对于字符范围已知的情况（如 ASCII），使用数组比 HashMap 更高效
    • 数组访问更快，缓存友好，代码更简洁

常见陷阱

  1. 忘记处理边界条件：

    • 需要检查 s.length() < t.length() 的情况
    • 需要处理 null 输入

  2. valid 的判断错误：

    1
    2
    3
    4
    5
    // 错误：只要 window[c] >= need[c] 就增加 valid
    if(window[c] >= need[c]) valid ++;

    // 正确：只有当 window[c] == need[c] 时才增加 valid
    if(window[c] == need[c]) valid ++;

    如果使用 >=，会导致 valid 被重复累加。

  3. 窗口长度计算错误：

    1
    2
    3
    4
    5
    // 错误：right 已经自增，不需要 +1
    minLen = right - left + 1;

    // 正确：right 已经指向下一个位置
    minLen = right - left;

  4. 使用 if 而非 while：

    1
    2
    3
    4
    5
    // 错误：只收缩一次
    if(valid == required) { ... }

    // 正确：持续收缩直到不满足条件
    while(valid == required) { ... }

相关问题

总结

这道题是滑动窗口算法的经典应用，也是Hard 难度的代表题目。它要求我们：

核心要点

  1. 滑动窗口 + 哈希数组：使用双指针维护窗口，数组记录字符计数
  2. valid 变量优化：通过跟踪满足条件的字符种类数，实现 $O(1)$ 判断
  3. 扩展与收缩策略：
    • 右指针扩展，寻找满足条件的窗口
    • 左指针收缩，寻找最短满足条件的子串

学习价值

这道题不仅考查滑动窗口的基本应用，还涉及：

  • 数据结构选择：数组 vs HashMap 的权衡
  • 算法优化技巧：使用 valid 变量避免重复计算
  • 边界条件处理：正确处理各种边界情况
  • 代码实现细节：指针移动、条件判断的精确控制

通过这道题，我们可以深刻理解滑动窗口算法在实际问题中的应用，并为解决类似的子串问题打下坚实基础。掌握这道题后，可以更好地解决其他滑动窗口变种问题。