【LeetCode 热题 100】76. 最小覆盖子串——（解法二）滑动窗口+数组优化

Problem: 76. 最小覆盖子串
题目：给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 “” 。

【LeetCode 热题 100】76. 最小覆盖子串——（解法一）滑动窗口+数组

整体思路

这段代码同样用于解决 “最小窗口子串” 问题，但它采用了比前一版更优化的滑动窗口实现。核心的改进在于，它避免了在每次窗口收缩时都调用一个 O(k) 的 isCoverd 函数来检查窗口的有效性，而是通过一个计数器 less 来实现 O(1) 的有效性判断。

算法的整体思路如下：

1. 初始化“需求”计数器：

   • 使用一个大小为 128 的整型数组 cnt。这个数组的含义非常巧妙：它首先被初始化为 t 中各字符的需求量。
   • 使用一个变量 less，它记录了当前窗口还缺少多少种类的字符才能满足 t 的需求。less 的初始值等于 t 中不同字符的种类数。

2. 滑动窗口的扩张与收缩：

   • 算法使用 l (left) 和 r (right) 两个指针定义滑动窗口。
   • 窗口扩张与“满足需求”：
     • 外层 for 循环驱动 r 指针向右移动，将新字符 c = s[r] 纳入窗口。
     • 执行 cnt[c]--，表示 c 这个字符的需求量减少了一个。
     • 如果 cnt[c] 在减一后恰好变为 0，这意味着对于字符 c，窗口内的数量正好满足了 t 的需求。此时，将 less--，表示还需满足的字符种类数减一。
   • 窗口校验与收缩：
     • 当 less == 0 时，说明当前窗口已经包含了 t 中所有种类的字符，并且每种字符的数量都已足够。这是一个有效的覆盖窗口。
     • 进入 while (less == 0) 循环，目的是在保持窗口有效的前提下，尽可能地向右移动左边界 l，以找到更短的窗口。
       a. 更新结果：比较当前窗口 [l, r] 的长度和已记录的最小长度，如果当前更短，则更新 ansLeft 和 ansRight。
       b. 收缩窗口：将左边界字符 x = s[l] 移出窗口。
       c. 更新“需求”：执行 cnt[x]++，表示对字符 x 的需求量增加了一个。
       d. 更新 less：如果 cnt[x] 在加一后恰好从 0 变为 1，这意味着窗口内字符 x 的数量现在不再满足 t 的需求了（因为我们刚刚移走了一个关键的x）。因此，将 less++，表示又多了一种需要满足的字符。
       e. 移动左边界：l++。
     • 这个 while 循环会持续进行，直到窗口不再有效（即 less 不再为0）。

3. 返回结果：

   • 遍历结束后，返回 ansLeft 和 ansRight 定义的最小子串。

这种方法通过 less 计数器，将判断窗口有效性的操作从 O(k) 降为了 O(1)，是解决此类问题的标准且最高效的模式。

完整代码

class Solution {
    /**
     * 在字符串 S 中查找包含字符串 t 所有字符的最小窗口子串（优化版）。
     * @param S 主字符串
     * @param t 目标字符串
     * @return 最小窗口子串，如果不存在则返回空字符串
     */
    public String minWindow(String S, String t) {
        // cnt: 字符频率计数器。初始时，它存储了 t 中需要的字符数量。
        int[] cnt = new int[128];
        // less: 记录还需要满足的字符种类数。
        int less = 0;
        
        // 步骤 1: 初始化“需求”计数器
        for (char c : t.toCharArray()) {
            // 如果是 t 中第一次遇到的字符种类，增加 less
            if (cnt[c] == 0) {
                less++;
            }
            // 增加该字符的需求量
            cnt[c]++;
        }
        
        char[] s = S.toCharArray();
        int m = s.length;
        // ansLeft, ansRight: 记录最终找到的最小窗口的左右边界
        int ansLeft = -1;
        int ansRight = m;
        // l 是滑动窗口的左边界
        int l = 0;
        
        // 步骤 2: 滑动窗口遍历主串 S
        for (int r = 0; r < m; r++) {
            char c = s[r];
            // a. 窗口扩张：将右边界字符 c 纳入窗口，其需求量减一
            cnt[c]--;
            // 如果字符 c 的需求量恰好被满足 (从 1 变为 0)，则待满足的种类数减一
            if (cnt[c] == 0) {
                less--;
            }
            
            // b. 窗口校验与收缩：当所有种类的字符都满足时 (less == 0)
            while (less == 0) {
                // 如果当前窗口比已记录的最小窗口更短，则更新结果
                if (ansRight - ansLeft > r - l) {
                    ansRight = r;
                    ansLeft = l;
                }
                
                // 尝试收缩窗口，将左边界字符 x 移出
                char x = s[l];
                // 归还字符 x 的需求量
                cnt[x]++;
                // 如果归还后，字符 x 的需求量从 0 变为 1，说明窗口不再满足对 x 的需求
                // 此时，待满足的字符种类数加一
                if (cnt[x] == 1) { // 注意这里是判断是否等于 1，因为 cnt[x]++ 之前是 0
                    less++;
                }
                // 左边界右移
                l++;
            }
        }
        
        // 步骤 3: 返回结果
        return ansLeft < 0 ? "" : S.substring(ansLeft, ansRight + 1);
    }
}

代码逻辑修正: 在 cnt[x]++ 之后，if 判断应该是 cnt[x] == 1，因为 cnt[x] 从 0 增加到 1，才代表这个字符从“满足”状态变为“不满足”状态。上面的注释已据此修正。

时空复杂度

时间复杂度：O(|S| + |t|)

1. 预处理 t：第一个 for 循环遍历 t 一次，时间复杂度为 O(|t|)。
2. 滑动窗口遍历 S：
   • 外层 for 循环的 r 指针遍历 S 一次，移动 |S| 次。
   • 内层 while 循环的 l 指针也只在 S 上从左到右移动一次。
   • 每个字符最多被 r 指针访问一次，被 l 指针访问一次。
   • 所有在循环内部的操作（数组读写、less 变量的增减）都是 O(1) 的。

综合分析：
总的时间复杂度是预处理时间加上两个指针的线性扫描时间，即 O(|t|) + O(|S|) = O(|S| + |t|)。这是解决此问题的最优时间复杂度。

空间复杂度：O(k) 或 O(1)

1. 主要存储开销：算法使用了整型数组 cnt 和字符数组 s。
   • cnt 数组的大小是 128，这是一个代表字符集大小 k 的常数。其空间复杂度为 O(k)。
   • s = S.toCharArray() 创建了 S 的一个副本，占用了 O(|S|) 的空间。
2. 分析视角：
   • 只考虑算法核心逻辑所需的额外辅助空间，主要是 cnt 数组。由于其大小是固定的，空间复杂度为 O(k)，即 O(1)。
   • 如果考虑 toCharArray() 的拷贝，则空间为 O(|S|).

综合分析：
算法的辅助空间复杂度为 O(k) (其中 k 为字符集大小)，可以视为 O(1)。

参考灵神