题目

给定字符串 s 和 t，在 s 中找出包含 t 所有字符的最短子串。

题目分析

这题不是普通的“最长合法窗口”，而是“最短满足窗口”。难点在于：

  • 你要先判断窗口什么时候已经满足要求
  • 满足后，还要尽可能继续缩小窗口

所以它比“无重复字符的最长子串”多了一层“覆盖计数”的管理。

方法一：直觉解法

最直接的办法是枚举所有子串，再检查是否覆盖 t。这显然能做，但复杂度会非常高。

方法二：优化思路

核心思路还是滑动窗口，但要维护两个计数：

  • need：目标字符串里每个字符需要多少次
  • window：当前窗口里每个字符已有多少次

当窗口已经满足所有需求时：

  • 尝试移动左边界缩小窗口
  • 每次缩之前更新当前最优答案

Go 实现

 1func minWindow(s string, t string) string {
 2    if len(t) == 0 || len(s) < len(t) {
 3        return ""
 4    }
 5
 6    need := make(map[byte]int)
 7    for i := 0; i < len(t); i++ {
 8        need[t[i]]++
 9    }
10
11    window := make(map[byte]int)
12    valid := 0
13    left := 0
14    bestStart, bestLen := 0, len(s)+1
15
16    for right := 0; right < len(s); right++ {
17        ch := s[right]
18        if _, ok := need[ch]; ok {
19            window[ch]++
20            if window[ch] == need[ch] {
21                valid++
22            }
23        }
24
25        for valid == len(need) {
26            if right-left+1 < bestLen {
27                bestStart = left
28                bestLen = right - left + 1
29            }
30
31            drop := s[left]
32            if _, ok := need[drop]; ok {
33                if window[drop] == need[drop] {
34                    valid--
35                }
36                window[drop]--
37            }
38            left++
39        }
40    }
41
42    if bestLen == len(s)+1 {
43        return ""
44    }
45    return s[bestStart : bestStart+bestLen]
46}

复杂度分析

  • 时间复杂度：O(n)
  • 空间复杂度：O(k)

易错点

  • valid 统计的是“满足要求的字符种类数”，不是字符总数
  • 更新最优答案要放在窗口仍然满足要求的时候
  • 收缩窗口时，先判断是否会破坏合法性，再减少计数

我的复盘

这题让我真正把滑动窗口从“会套模板”推进到了“会维护约束”。一旦想清楚窗口合法条件和失效条件，复杂问题也能拆开处理。