LeetCode 补拙笔记

0. 前言

• 日期：2026.06.20
• 题目：76. 最小覆盖子串
• 难度：困难
• 标签：滑动窗口、哈希表、双指针

1. 题目理解

问题描述 给定两个字符串 s 和 t，在 s 中找出包含 t 所有字符的最短连续子串，不存在则返回空字符串。

示例

输入：s = "ADOBECODEBANC", t = "ABC" 输出："BANC" 解释：子串 BANC 包含 A、B、C 且长度最短。

2. 解题思路

核心观察

1. 滑动窗口双指针：右指针扩张窗口纳入字符，左指针收缩窗口寻找最小合法区间；
2. 用哈希表 need 记录目标字符需求，window 记录窗口内字符计数，valid 记录满足计数的字符种类；
3. 优化方向：用长度128的ASCII数组替代HashMap，消除装箱、containsKey分支；通过数组数值直接判断匹配，精简多层if条件。

算法步骤

1. 统计字符串t各字符所需数量；
2. 右指针不断向右扩张窗口，更新窗口字符计数，统计匹配成功字符数valid；
3. 当valid等于目标字符种类，窗口合法，循环收缩左边界更新最小子串；
4. 收缩时若移除字符使计数不再达标，valid自减，跳出收缩循环；
5. 遍历完成根据最小长度截取结果。

3. 代码实现

package lc0_lc99.lc76;

import java.util.HashMap;

class Solution {
    public String minWindow(String s, String t) {
        HashMap<Character, Integer> need = new HashMap<>();
        HashMap<Character, Integer> window = new HashMap<>();
        for (char c : t.toCharArray()) {
            need.put(c, need.getOrDefault(c, 0) + 1);
        }
        int left = 0, right = 0;
        int valid = 0;
        int start = 0;
        int minLen = Integer.MAX_VALUE;

        while (right < s.length()) {
            char c = s.charAt(right);
            right++;
            if (need.containsKey(c)) {
                window.put(c, window.getOrDefault(c, 0) + 1);
                if (window.get(c).equals(need.get(c))) {
                    valid++;
                }
            }
            // 所有字符匹配完成，收缩左边界
            while (valid == need.size()) {
                int curLen = right - left;
                if (curLen < minLen) {
                    minLen = curLen;
                    start = left;
                }
                char d = s.charAt(left);
                left++;
                if (need.containsKey(d)) {
                    if (window.get(d).equals(need.get(d))) {
                        valid--;
                    }
                    window.put(d, window.get(d) - 1);
                }
            }
        }
        return minLen == Integer.MAX_VALUE ? "" : s.substring(start, start + minLen);
    }
}

4. 代码优化说明

class Solution {
public String minWindow(String s, String t) {
    // ASCII数组替代HashMap，消除字符装箱与containsKey分支
    int[] need = new int[128];
    int[] window = new int[128];
    int type = 0;
    // 统计目标字符需求，记录不同字符种类
    for (char ch : t.toCharArray()) {
        if (need[ch]++ == 0) type++;
    }
    int l = 0, r = 0, valid = 0;
    int minStart = 0, minLen = Integer.MAX_VALUE;
    while (r < s.length()) {
        char rc = s.charAt(r++);
        window[rc]++;
        // 字符计数刚好匹配需求，匹配种类+1
        if (window[rc] == need[rc] && need[rc] != 0) valid++;
        // 窗口合法，收缩左边界
        while (valid == type) {
            int len = r - l;
            // 更新最短子串
            if (len < minLen) {
                minLen = len;
                minStart = l;
            }
            char lc = s.charAt(l++);
            // 移除后不再满足需求，匹配种类-1
            if (window[lc] == need[lc] && need[lc] != 0) valid--;
            window[lc]--;
        }
    }
    return minLen == Integer.MAX_VALUE ? "" : s.substring(minStart, minStart + minLen);
}
}

5. 复杂度分析

• HashMap原版 时间复杂度：$O(n+m)$，n为s长度、m为t长度；大量containsKey、equals条件分支，哈希存取存在常数开销 空间复杂度：$O(1)$，仅26个字母相关键值对，哈希表容量恒定
• ASCII数组优化版 时间复杂度：$O(n+m)$，无哈希查询、字符装箱操作，数组直接下标访问，删除多层if分支判断 空间复杂度：$O(1)$，固定128长度数组，内存占用稳定

6. 总结

• 核心：双指针滑动窗口，通过匹配字符种类判断窗口合法性；
• 优化亮点：使用ASCII数组替换HashMap，消除哈希相关分支；统一字符匹配判断逻辑，精简嵌套if；
• 关键变量：valid记录完全匹配的字符种类，是判断窗口是否合法的核心标记。