当前位置： 首页 > ops >正文

【Leetcode hot 100】76.最小覆盖字串

ops 2025/8/15 7:52:46

一、题目理解

先明确问题：
给两个字符串s和t，请在s中找到最短的子串，使得这个子串包含t中所有字符（包括重复的字符，比如t中有2个’a’，子串中至少也要有2个’a’）。如果没有这样的子串，返回空字符串。

举个例子：

  • 输入s = "ADOBECODEBANC"，t = "ABC"
  • 输出"BANC"（因为它包含’A’、‘B’、‘C’，且是最短的）

二、核心思路：滑动窗口 + 哈希表

为什么用滑动窗口？
因为我们要找的是连续的子串，且需要动态调整子串的范围（扩大或缩小）来找到“最小”的有效子串。滑动窗口通过左右两个指针维护一个“窗口”，能高效地在一次遍历中完成搜索。

为什么用哈希表？
我们需要跟踪两个信息：

  1. t中每个字符需要多少个（比如t=ABC，需要’A’:1, ‘B’:1, ‘C’:1）。
  2. 当前窗口中每个字符有多少个（比如窗口是ADOBEC，则’A’:1, ‘D’:1, ‘O’:1, ‘B’:1, ‘E’:1, ‘C’:1）。

通过比较这两个信息，就能判断当前窗口是否“有效”（即包含t的所有字符）。

三、具体步骤拆解

我们分4步来实现：

步骤1：初始化“需求”和“当前窗口”的字符计数

  • 用两个数组（need和window，大小128，对应ASCII码）代替哈希表（效率更高，因为字符是英文字母）。
  • need[c]：记录字符c在t中需要出现的次数（比如t中有2个’a’，则need['a']=2）。
  • window[c]：记录当前窗口中字符c出现的次数。

同时，统计t中不同字符的种类数（记为valid）。比如t=ABC有3种字符，valid=3。

步骤2：扩大窗口（移动右指针）

  • 右指针right从0开始，依次遍历s中的每个字符c。
  • 每遍历一个字符，就将window[c]加1（更新当前窗口的计数）。
  • 当window[c]的数量恰好等于need[c]时（说明这个字符的需求被满足了），就将valid减1（表示一种字符已满足）。

步骤3：当窗口有效时，缩小窗口（移动左指针）

  • 当valid=0时，说明当前窗口已经包含t中所有字符（有效窗口）。
  • 此时尝试移动左指针left，缩小窗口范围，寻找更短的有效窗口：
    • 记录当前窗口的长度，如果比之前的“最小长度”更短，则更新最小长度和起始位置。
    • 将左指针指向的字符d从窗口中移除（window[d]--）。
    • 如果window[d]的数量小于need[d]（说明这个字符的需求不再满足），则valid加1（此时窗口不再有效，停止缩小）。

步骤4：返回结果

  • 遍历结束后，如果找到过有效窗口，就返回最短的子串；否则返回空字符串。

四、示例演示（结合代码逻辑）

以s = "ADOBECODEBANC"，t = "ABC"为例：

  1. 初始化：
    need['A']=1, need['B']=1, need['C']=1，其他为0；valid=3。

  2. 扩大窗口（右指针移动）：

    • right=0（字符’A’）：window['A']=1，等于need['A']，valid=2。
    • right=1（‘D’）：window['D']=1（不影响valid，因为need['D']=0）。
    • right=2（‘O’）：同上，valid不变。
    • right=3（‘B’）：window['B']=1，等于need['B']，valid=1。
    • right=4（‘E’）：不影响。
    • right=5（‘C’）：window['C']=1，等于need['C']，valid=0（窗口有效！当前窗口是[0,5]，即"ADOBEC"，长度6）。

  3. 缩小窗口（左指针移动）：

    • 记录当前窗口长度6。
    • 左指针left=0（字符’A’）：window['A']--变为0，此时window['A'] < need['A']，valid=1（窗口不再有效）。左指针移到1。

  4. 继续扩大窗口：
    右指针继续移动，直到再次valid=0（比如窗口包含CODEBANC中的部分字符），重复缩小步骤，最终找到最短窗口"BANC"（长度4）。

五、Java代码实现

class Solution {public String minWindow(String s, String t) {// 初始化need和window数组（英文字母ASCII码范围0-127）int[] need = new int[128];int[] window = new int[128];// 填充need数组，统计t中每个字符的需求for (char c : t.toCharArray()) {need[c]++;}int left = 0; // 左指针int right = 0; // 右指针int valid = 0; // 已满足的字符种类数int start = 0; // 最小窗口的起始索引int len = Integer.MAX_VALUE; // 最小窗口的长度// 统计t中不同字符的种类数（初始化valid）for (int i = 0; i < 128; i++) {if (need[i] > 0) {valid++;}}// 扩大窗口（移动右指针）while (right < s.length()) {char c = s.charAt(right);right++; // 右指针右移// 如果当前字符是t中需要的，更新windowif (need[c] > 0) {window[c]++;// 当window中该字符数量恰好满足需求时，减少validif (window[c] == need[c]) {valid--;}}// 当窗口有效（valid=0），尝试缩小窗口while (valid == 0) {// 更新最小窗口if (right - left < len) {start = left;len = right - left;}// 左指针指向的字符即将被移除char d = s.charAt(left);left++; // 左指针右移// 如果移除的是t中需要的字符，检查是否还满足需求if (need[d] > 0) {// 若window中数量从满足变为不满足，增加validif (window[d] == need[d]) {valid++;}window[d]--;}}}// 若没找到有效窗口，返回空串；否则返回最短子串return len == Integer.MAX_VALUE ? "" : s.substring(start, start + len);}
}

六、关键细节总结

  1. 为什么用数组而不是HashMap？
    英文字母的ASCII码范围固定（0-127），用数组访问速度更快，且避免了哈希表的哈希计算开销。

  2. valid的作用？
    它是优化的核心！通过valid判断窗口是否有效，避免了每次都遍历整个need数组（从O(128)优化到O(1)），最终使时间复杂度达到O(m+n)（m是s长度，n是t长度）。

  3. 窗口缩小的时机？
    只有当窗口有效（valid=0）时才缩小，确保我们只在“有效窗口”中寻找更短的解。

七、练习与思考

  • 尝试用HashMap实现一遍，对比数组的效率差异。
import java.util.HashMap;
import java.util.Map;public class Solution {public String minWindow(String s, String t) {// 边界处理：s或t为空，或s长度小于t，直接返回空if (s == null || t == null || s.length() == 0 || t.length() == 0 || 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);}Map<Character, Integer> window = new HashMap<>(); // 当前窗口的字符计数int left = 0, valid = 0; // valid：满足need数量的字符种类数int start = 0, minLen = Integer.MAX_VALUE; // 记录最小子串的起始位置和长度for (int right = 0; right < s.length(); right++) {char c = s.charAt(right);// 更新当前窗口的字符计数window.put(c, window.getOrDefault(c, 0) + 1);// 若当前字符满足t的数量要求，更新validif (need.containsKey(c) && window.get(c).intValue() == need.get(c).intValue()) {valid++;}// 当窗口包含t所有字符时，尝试收缩左边界while (valid == need.size()) {int currentLen = right - left + 1;// 更新最小子串if (currentLen < minLen) {minLen = currentLen;start = left;}// 收缩左边界，移除左指针的字符char leftChar = s.charAt(left);left++;// 若移除的字符是t需要的，检查是否影响validif (need.containsKey(leftChar)) {// 移除前，该字符数量刚好满足need，移除后会不满足，故valid--if (window.get(leftChar).intValue() == need.get(leftChar).intValue()) {valid--;}window.put(leftChar, window.get(leftChar) - 1);}}}// 若未找到有效子串，返回空；否则返回最小子串return minLen == Integer.MAX_VALUE ? "" : s.substring(start, start + minLen);}
}
  • 思考：如果s和t包含 Unicode 字符（不止英文字母），该如何修改代码？

当s和t包含Unicode字符时，核心修改思路是用哈希表（HashMap）替代固定大小的数组，因为Unicode字符的范围远超ASCII（0-127），无法用有限大小的数组覆盖所有可能的字符。以下是具体的修改方案：

关键修改点分析

  1. 字符计数容器替换：
    原代码用int[] need = new int[128]和int[] window = new int[128]存储字符计数（仅支持ASCII），需替换为HashMap<Character, Integer>，因为Character可以表示所有Unicode字符（包括中文、日文、特殊符号等）。

  2. 初始化逻辑调整：
    统计t中Unicode字符的需求时，直接遍历t的每个字符（无论是否为Unicode），用HashMap记录每个字符的出现次数。

  3. 窗口更新逻辑适配：
    扩大/缩小窗口时，对Unicode字符的处理与原逻辑一致（更新计数、判断是否满足需求），但需通过HashMap的getOrDefault等方法操作，避免数组越界。

  4. 计数比较注意事项：
    由于HashMap中存储的是Integer对象，比较计数时需用intValue()获取实际数值（避免因Integer缓存机制导致的==判断错误）。

修改后的代码实现

import java.util.HashMap;
import java.util.Map;public class Solution {public String minWindow(String s, String t) {// 边界处理：空字符串或s长度小于t，直接返回空if (s == null || t == null || s.length() == 0 || t.length() == 0 || s.length() < t.length()) {return "";}// 用HashMap存储t中所有Unicode字符的需求（键：字符，值：需要的次数）Map<Character, Integer> need = new HashMap<>();for (char c : t.toCharArray()) {// 无论c是否为Unicode，均统计次数need.put(c, need.getOrDefault(c, 0) + 1);}// 用HashMap存储当前窗口中所有Unicode字符的计数Map<Character, Integer> window = new HashMap<>();int left = 0; // 左指针int valid = 0; // 已满足需求的字符种类数（初始为need中不同字符的数量）int start = 0; // 最短子串的起始索引int minLen = Integer.MAX_VALUE; // 最短子串的长度// 扩大窗口（移动右指针）for (int right = 0; right < s.length(); right++) {char c = s.charAt(right); // c可能是Unicode字符// 更新当前窗口的字符计数window.put(c, window.getOrDefault(c, 0) + 1);// 若当前字符是t中需要的，且窗口中该字符的数量恰好满足需求，更新validif (need.containsKey(c) && window.get(c).intValue() == need.get(c).intValue()) {valid++;}// 当窗口包含t中所有字符（valid等于need的大小），尝试缩小窗口while (valid == need.size()) {// 更新最短子串int currentLen = right - left + 1;if (currentLen < minLen) {minLen = currentLen;start = left;}// 缩小左边界，移除左指针指向的字符（可能是Unicode）char leftChar = s.charAt(left);left++;// 若移除的字符是t中需要的，检查是否仍满足需求if (need.containsKey(leftChar)) {// 若移除前数量恰好满足需求，移除后将不满足，故valid减1if (window.get(leftChar).intValue() == need.get(leftChar).intValue()) {valid--;}// 更新窗口中该字符的计数window.put(leftChar, window.get(leftChar) - 1);}}}// 若未找到有效子串，返回空；否则返回最短子串return minLen == Integer.MAX_VALUE ? "" : s.substring(start, start + minLen);}
}

核心逻辑说明

  • 哈希表适配Unicode：HashMap<Character, Integer>可以存储任何Character类型的键（包括所有Unicode字符），解决了数组无法覆盖大范围字符的问题。
  • 计数比较安全性：通过intValue()获取Integer的实际数值进行比较，避免了==对Integer对象比较时的缓存机制干扰（例如Integer.valueOf(128) == Integer.valueOf(128)为false）。
  • 逻辑一致性：滑动窗口的核心逻辑（扩大窗口→判断有效→缩小窗口→更新最短子串）与原代码完全一致，仅替换了字符计数的容器，保证了算法的高效性（时间复杂度仍为O(m+n)，m和n分别为s和t的长度）。

通过以上修改，代码可完美支持包含Unicode字符的字符串处理。

http://www.xdnf.cn/news/17705.html

相关文章：

  • 【HarmonyOS】Window11家庭中文版开启鸿蒙模拟器失败提示未开启Hyoer-V
  • SwiftUI 页面弹窗操作
  • 用飞算JavaAI一键生成电商平台项目：从需求到落地的高效实践
  • 使用免费API开发口播数字人
  • [机器学习]07-基于多层感知机的鸢尾花数据集分类
  • c++中的Lambda表达式详解
  • Java基础07——基本运算符(本文为个人学习笔记，内容整理自哔哩哔哩UP主【遇见狂神说】的公开课程。 ＞ 所有知识点归属原作者，仅作非商业用途分享)
  • k8s+isulad 网络问题
  • 如何使用 AI 大语言模型解决生活中的实际小事情？
  • 【P81 10-7】OpenCV Python【实战项目】——车辆识别、车流统计（图像/视频加载、图像运算与处理、形态学、轮廓查找、车辆统计及显示）
  • 网络协议序列化工具Protobuf
  • 4.1vue3的setup()
  • 2019 GPT2原文 Language Models are Unsupervised Multitask Learners - Reading Notes
  • Kotlin Data Classes 快速上手
  • Qt TCP 客户端对象生命周期与连接断开问题解析
  • 解锁Prompt秘籍：框架、技巧与指标全解析
  • Windows 11操作系统 Git命令执行速度慢
  • SpringMVC基本原理和配置
  • 第2节 如何计算神经网络的参数：AI入门核心逻辑详解
  • pytorch学习笔记-加载现有的网络模型(VGG16)、增加/修改其中的网络层(修改为10分类)
  • 云计算-多服务集群部署实战指南：从JumpServer到Kafka、ZooKeeper 集群部署实操流程
  • 70亿参数让机器人“开窍“：英伟达Cosmos Reason如何让AI理解物理世界
  • 分段锁和限流的间接实现
  • 基于51单片机的手机蓝牙控制8位LED灯亮灭设计
  • Day19 C 语言标准 IO 机制
  • 深度学习——03 神经网络（2）-损失函数
  • 2021 年全国硕士研究生招生考试真题笔记
  • AI时代程序员的进化：从代码工人到创意架构师-优雅草卓伊凡引言：AI浪潮下的职业重构
  • 若依前后端分离版学习笔记（九）——登录和操作日志
  • OpenBMC中的BMCWeb：架构、原理与应用全解析