知序
返回
保存草稿
发布
H1
H2
H3
1
2
3
Excalidraw 图
AI 写作
AI 优化
目录
输入内容后显示目录
Markdown
# 03 - 最小覆盖子串 ## 题目(LeetCode 76) 给定字符串 s 和 t,找出 s 中包含 t 所有字符的最小子串。 ``` 输入:s = "ADOBECODEBANC", t = "ABC" 输出:"BANC" ``` ## 大白话理解 窗口不断右扩,直到包含了 t 的所有字符,然后左缩找最小窗口。 ## 代码 ```java public String minWindow(String s, String t) { if (s == null || t == null || s.length() < t.length()) { return ""; } // 统计 t 中每个字符需要的个数 Map<Character, Integer> need = new HashMap<>(); for (char c : t.toCharArray()) { need.put(c, need.getOrDefault(c, 0) + 1); } int left = 0; int valid = 0; // 已满足条件的字符种类数 int start = 0, len = Integer.MAX_VALUE; // 窗口中的字符统计 Map<Character, Integer> window = new HashMap<>(); for (int right = 0; right < s.length(); right++) { char c = s.charAt(right); // 右扩:如果是 t 中需要的字符,更新窗口数据 if (need.containsKey(c)) { window.put(c, window.getOrDefault(c, 0) + 1); if (window.get(c).equals(need.get(c))) { valid++; // 该字符种类满足条件 } } // 左缩:窗口已覆盖 t 的所有字符,尝试缩小窗口 while (valid == need.size()) { //如果当前值更小, 更新最小覆盖子串 if (right - left + 1 < len) { start = left; len = right - left + 1; } 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 len == Integer.MAX_VALUE ? "" : s.substring(start, start + len); } ``` ## 核心逻辑 ``` need[c]:字符 c 在 t 中需要几个 window[c]:当前窗口中字符 c 有几个 valid:已满足条件的字符种类数(window[c] >= need[c] 的种类数) 右扩:window[c]++,如果 window[c] == need[c] → valid++ 左缩: 先判断:如果 window[d] == need[d],移除后会破坏条件 → valid-- 再减少:window[d]-- valid == need.size() 时窗口合法,记录答案并收缩 ``` ## 手动模拟(s="ADOBECODEBANC", t="ABC") ``` need = {A:1, B:1, C:1},need.size() = 3 right=0, c='A': window={A:1}, A满足 → valid=1 right=1, c='D': 不在need,跳过 right=2, c='O': 不在need,跳过 right=3, c='B': window={A:1,B:1}, B满足 → valid=2 right=4, c='E': 不在need,跳过 right=5, c='C': window={A:1,B:1,C:1}, C满足 → valid=3 valid==3,开始左缩: 窗口 [0,5] = "ADOBEC",len=6,start=0 left=0, d='A': window[A]==need[A]=1 → valid=2,window={A:0,B:1,C:1},left=1 valid!=3,停止左缩 right=6, c='O': 跳过 right=7, c='D': 跳过 right=8, c='E': 跳过 right=9, c='B': window={A:0,B:2,C:1},B已经>need,valid不变=2 right=10, c='A': window={A:1,B:2,C:1}, A满足 → valid=3 valid==3,开始左缩: 窗口 [1,10] = "DOBECODEBA",len=10 > 6,不更新 left=1, d='D': 不在need,left=2 窗口 [2,10] = "OBECODEBA",len=9 > 6,不更新 left=2, d='O': 不在need,left=3 窗口 [3,10] = "BECODEBA",len=8 > 6,不更新 left=3, d='B': window[B]=2 > need[B]=1,不破坏 → valid不变,window={A:1,B:1,C:1},left=4 窗口 [4,10] = "ECODEBA",len=7 > 6,不更新 left=4, d='E': 不在need,left=5 窗口 [5,10] = "CODEBA",len=6,不更新(等于当前最小) left=5, d='C': window[C]==need[C]=1 → valid=2,window={A:1,B:1,C:0},left=6 valid!=3,停止左缩 right=11, c='N': 跳过 right=12, c='C': window={A:1,B:1,C:1}, C满足 → valid=3 valid==3,开始左缩: 窗口 [6,12] = "ODEBANC",len=7 > 6,不更新 left=6, d='O': 不在need,left=7 窗口 [7,12] = "DEBANC",len=6,不更新(等于当前最小) left=7, d='D': 不在need,left=8 窗口 [8,12] = "EBANC",len=5 < 6 → start=8,len=5 left=8, d='E': 不在need,left=9 窗口 [9,12] = "BANC",len=4 < 5 → start=9,len=4 left=9, d='B': window[B]==need[B]=1 → valid=2,left=10 valid!=3,停止左缩 最终:start=9,len=4 → s.substring(9, 13) = "BANC" ✓ ``` ## 复杂度 - 时间:O(n),left 和 right 各走一遍 - 空间:O(字符集大小) ## 一句话总结 右扩直到覆盖 t 的所有字符,左缩找最小窗口。`valid == need.size()` 时窗口合法,先记录答案再收缩。 --- 上一篇:[02 - 无重复字符的最长子串](./02-longest-substring.md) | 下一篇:[04 - 找到所有字母异位词](./04-find-anagrams.md)
预览
发布文章
添加摘要让读者更快了解文章内容
取消
确认发布
AI 写作助手
输入一个主题,AI 将为你生成一篇 Markdown 博客文章
AI 正在写作中...
取消
开始生成
AI 优化助手
描述你的修改需求,AI 将在原文基础上进行补充或微调
AI 正在优化中...
取消
开始优化
画布
从已有图里选
✕
图名
保存后生成 /images/excalidraw/<图名>.svg(只能用字母、数字、短横线、下划线、点)
取消
保存并插入