【算法】滑动窗口—最小覆盖子串
题目
”最小覆盖子串“问题,难度为Hard,题目如下:
给你两个字符串 S 和 T,请你在 S 中找到包含 T 中全部字母的最短子串。如果 S 中没有这样一个子串,则算法返回空串,如果存在这样一个子串,则可以认为答案是唯一的。
比如输入 S = "ADBECFEBANC",T = "ABC",算法应该返回 "BANC"。
如果我们使用暴力解法,代码大概是这样的:
for (int i = 0; i < s.size; i++) {
for (int j = i + 1; j < s.size; j++) {
if [i : j] 包含 t 的所有字母:
更新答案
}
}
思路很简单,但显然不是我们想要的。
滑动窗口思路分析
1.我们在字符串 S 中使用双指针中的左、右指针技巧,初始化 left = right = 0,把索引左闭右开区间 [left, right) 称为一个”窗口“。
2.先不断地增加 right 指针扩大窗口 [left, right),直到窗口中的字符串符合要求(包含了 T 中的所有字符)。
3.此时,停止增加 right,转而不断增加 left 指针缩小窗口 [left, right),直到窗口中的字符串不再符合要求(不包含 T 中所有字符了)。同时,每次增加 left,都要更新一轮结果。
4.重复第2和第3步,直到 right 到达字符 S 的尽头。
第2步相当于在寻找一个”可行解“,然后第3步在优化这个”可行解“,最终找到最优解,也就是最短的覆盖子串。左、右指针轮流前进 ,窗口大小增增减减,窗口不断向右滑动,这就是”滑动窗口“这个名字的来历。
下面画图理解一下这个思路。needs 和 window 相当于计数器,分别记录 T 中字符出现次数和”窗口“中的相应字符的出现次数。
初始状态:

增加 right,直到窗口 [left, right) 包含了 T 中所有字符:

现在开始增加 left,缩小窗口 [left, right):

直到窗口中的字符串不再符合要求,left 不再继续移动:

之后重复上述过程,先移动 right,再移动 left······直到 right 指针到达字符串 S 的末端,算法结束。现在来看看滑动窗口代码框架怎么用。
首先,初始化 window 和 need 两个哈希表,记录窗口中的字符和需要凑齐的字符:
Map<Character, Integer> need = new HashMap<>();
Map<Character, Integer> window = new HashMap<>();
for (int i = 0; i < t.length(); i++) {
char key = t.charAt(i);
need.put(key, need.getOrDefault(key, 0) + 1);
}
然后,使用 left 和 right 变量初始化窗口的两端,不要忘了,区间 [left, right) 是左闭右开的,所以初始情况下窗口没有包含任何元素:
int left = 0, right = 0, valid = 0;
while (right < s.length()) { // 开始滑动 }
其中,valid 变量表示窗口中满足 need 条件的字符个数,如果 valid 和 need.size 的大小相同,则说明窗口已满足条件,已经完全覆盖了串 T。
现在开始套模板,只需要思考以下4个问题:
1.当移动 right 扩大窗口,即加入字符时,应该更新哪些数据?
2.什么条件下,窗口应该暂停扩大,开始移动 left 缩小窗口?
3.当移动 left 缩小窗口,即移出字符时,应该更新哪些数据?
4.我们要的结果应该在扩大窗口时还是缩小窗口时进行更新?
一般来说,如果一个字符进入窗口,应该增加 window 计数器;如果一个字符移出窗口,应该减少 window 计数器;当 valid 满足 need 时应该收缩窗口;收缩窗口的时候应该更新最终结果。
下面是完整代码:
package SlidingWindow;import java.util.HashMap;
import java.util.Map;// leetcode 017 最小覆盖子串
public class MCS {public String slidingWindow(String s, String t) {Map<Character, Integer> need = new HashMap<>();Map<Character, Integer> window = new HashMap<>();for (int i = 0; i < t.length(); i++) {char key = t.charAt(i);need.put(key, need.getOrDefault(key, 0) + 1);}int left = 0, right = 0, valid = 0; // valid 表示窗口中满足 need 条件的字符个数// 记录最小覆盖子串的启始索引及长度int start = 0, len = Integer.MAX_VALUE;while (right < s.length()) {// c 是将要移入窗口的字符char c = s.charAt(right);// 右移窗口right++;// 进行窗口内数据的一系列更新if (need.containsKey(c)) {window.put(c, window.getOrDefault(c, 0) + 1);if (window.getOrDefault(c, 0).equals(need.getOrDefault(c, 0))) { // window[c] == need[c]valid++;}}/*** debug 输出的位置***/System.out.println("window:(" + left + ", " + right + ")");/*********************/// 判断左侧窗口是否要收缩while (valid == need.size()) { // window need shrink —窗口需要收缩// 在这里更新最小覆盖子串if (right - left < len) {start = left;len = right - left;}// d 是将要移出窗口的字符char d = s.charAt(left);// 左移窗口left++;// 进行窗口内数据的一系列更新if (need.containsKey(d)) {if (window.getOrDefault(d, 0).equals(need.getOrDefault(d, 0))) {valid--;}window.put(d, window.getOrDefault(d, 0) - 1);}}}// 返回最小覆盖子串return len == Integer.MAX_VALUE ? "" : s.substring(start, start + len); // s.substring(start, start + len) == C++ 中的 s.substr(start, len)}public static void main(String[] args) {MCS mcs = new MCS();String str = mcs.slidingWindow("ADOBECODEBANC", "ABC");System.out.println(str);}}
相关文章:
【算法】滑动窗口—最小覆盖子串
题目 ”最小覆盖子串“问题,难度为Hard,题目如下: 给你两个字符串 S 和 T,请你在 S 中找到包含 T 中全部字母的最短子串。如果 S 中没有这样一个子串,则算法返回空串,如果存在这样一个子串,则可…...
“Fast-forward“ in git-pull result
当你执行 git pull 并且结果显示 Fast-forward 时,这意味着你的本地分支可以直接快进到远程分支的最新提交,没有任何冲突或者需要合并的内容。具体来说,Fast-forward 是一种合并方式,它的特点是将当前分支的指针直接移动到远程分支…...
Oracle(133)如何创建表空间(Tablespace)?
在Oracle数据库中,表空间(Tablespace)是存储数据的逻辑单位,它由一个或多个数据文件组成。表空间是数据库数据管理的基本结构,了解如何创建表空间对于数据库管理员至关重要。 创建表空间的基本语法 创建表空间的基本…...
Linux中权限和指令
💥1、Linux基本指令 1.1 mv 指令 mv指令是move的缩写,用来移动或重命名文件、目录,经常用来备份文件或目录。 mv old_name new_name: 重命名文件或目录mv file /path/to/directory: 移动文件到指定目录 roothcss-ecs…...
本地镜像发布到阿里云
本地镜像发布到阿里云 登录阿里云容器镜像服务配置 Docker 登录阿里云容器镜像服务标记你的 Docker 镜像推送镜像到阿里云验证使用阿里云镜像注意事项 将 Docker 本地镜像发布到阿里云(Alibaba Cloud)容器镜像服务(Container Registry&#x…...
【Linux】【Vim】Vim 基础
Vim/Gvim 基础 文本编辑基础编辑操作符命令和位移改变文本重复改动Visual 模式移动文本(复制、粘贴)文本对象替换模式 光标移动以 word 为单位移动行首和行尾行内指定单字符移动到匹配的括号光标移动到指定行滚屏简单查找 /string标记 分屏vimdiff 文本编辑 基础编辑 Normal 模…...
计算机人工智能前沿进展-大语言模型方向-2024-09-18
计算机人工智能前沿进展-大语言模型方向-2024-09-18 1. The Application of Large Language Models in Primary Healthcare Services and the Challenges W YAN, J HU, H ZENG, M LIU, W LIANG - Chinese General Practice, 2024 人工智能大语言模型在基层医疗卫生服务中的应…...
ubuntu24安装vivado24(安装并解决若干错误)
目录 安装方法:问题1:解决办法: 问题2:解决方法: 安装完成: 安装方法: 注意:内存最好预留80G空闲的。 安装好大小: 安装依赖库: sudo apt-get update sud…...
CSS实现文本溢出省略号或完整显示
目录 前言1. 省略号2. 完整展示3. Demo 前言 文本内容超出容器宽度的问题,为了保持页面布局的整洁,通常会使用省略号来隐藏多余的内容 一共有两种方式: 设定省略号完整展示 1. 省略号 文本溢出时显示省略号 .item-value {flex-basis: 7…...
three.js PropertyBinding和PropertyMixer
PropertyBinding 对场景图中某一真实属性的引用,内部使用。 构造器 PropertyBinding( rootNode : Object3D, path, parsedPath ) -- rootNode: -- path -- parsedPath (可选) 属性 # .path : Number # .parsedPath : Number # .node : Number # .rootNode …...
ssh远程连接try1账号切换tips
1,创建拥有sudo权限的用户: 在root下 sudo adduser bio sudo vim /etc/sudoers //修改添加如下: bio ALL(ALL) ALL //bio用户就拥有了root权限参考:https://github.com/isLishude/blog/issues/70 2,修改ssh配置 …...
C++之第十二课
课程列表 哎呀呀,失踪人口回归了!(前段时间跑去B站了,久等了) 今天来讲——数组 有一道题是这样的: 有n个数,请输出其中最大的数。 原来我们就要: int a,b,c... 但是——数组…...
Linux硬连接、软连接和复制的区别
硬连接、软连接和复制在Linux系统中的主要区别体现在以下三点: 文件链接的方式文件独立性文件系统的操作上。 一、硬连接 1. 硬连接是通过ln命令创建的,它为文件创建别名,与源文件共享同一inode号码,因此硬连接和源文件实际…...
基于STM32的无人小车自主避障系统设计
文章目录 前言资料获取设计介绍功能介绍设计程序具体实现截图参考文献设计获取 前言 💗博主介绍:✌全网粉丝10W,CSDN特邀作者、博客专家、CSDN新星计划导师,一名热衷于单片机技术探索与分享的博主、专注于 精通51/STM32/MSP430/AVR等单片机设…...
杂牌鼠标侧键设置
X-Mouse Button Control修改侧键基本功能介绍-CSDN博客 下载链接 【X-Mouse汉化版】X-Mouse中文版 v2.19.2 绿色版(支持Win10)-开心电玩 (kxdw.com)...
Android WebView H5 Hybrid 混和开发
对于故乡,我忽然有了新的理解:人的故乡,并不止于一块特定的土地,而是一种辽阔无比的心情,不受空间和时间的限制;这心情一经唤起,就是你已经回到了故乡。——《记忆与印象》 前言 移动互联网发展…...
智源推出下一代检索增强大模型框架MemoRAG
北京智源人工智能研究院与中国人民大学高瓴人工智能学院联合发布了一款创新的人工智能模型框架——MemoRAG。该框架基于长期记忆,旨在推动检索增强生成(RAG)技术的发展,使其能够处理更复杂的任务,而不仅限于简单的问答…...
【AprilTag】视觉定位实战 | 使用 ROS 驱动的 USB 摄像头进行相机标定与 AprilTag 识别
写在前面: 🌟 欢迎光临 清流君 的博客小天地,这里是我分享技术与心得的温馨角落。📝 个人主页:清流君_CSDN博客,期待与您一同探索 移动机器人 领域的无限可能。 🔍 本文系 清流君 原创之作&…...
[数据集][目标检测]俯拍航拍森林火灾检测数据集VOC+YOLO格式6116张2类别
数据集格式:Pascal VOC格式YOLO格式(不包含分割路径的txt文件,仅仅包含jpg图片以及对应的VOC格式xml文件和yolo格式txt文件) 图片数量(jpg文件个数):6116 标注数量(xml文件个数):6116 标注数量(txt文件个数):6116 标注…...
windows10下tomcat安装及配置教程
Apache Tomcat是一个开源的、轻量级的Servlet容器,广泛用于运行Java Web应用程序。以下是Tomcat安装及配置的基本步骤,根据搜索结果整理: 一、安装前的准备工作 确保你的计算机上已经安装了Java Development Kit (JDK),因为Tomc…...
Adobe软件非正版弹窗终极解决方案:PS/Ai/PR/AE禁用提示一键清除指南
1. Adobe弹窗问题的根源分析 最近不少朋友打开Photoshop、Illustrator这些Adobe软件时,突然跳出一个烦人的提示框:"Your non-genuine Adobe app will be disabled soon"。这个警告不仅影响使用体验,严重时还会导致软件直接罢工。作…...
AQS深度探索:以ReentrantLock看Java并发编程的高效实现
在技术领域,我们常常被那些闪耀的、可见的成果所吸引。今天,这个焦点无疑是大语言模型技术。它们的流畅对话、惊人的创造力,让我们得以一窥未来的轮廓。然而,作为在企业一线构建、部署和维护复杂系统的实践者,我们深知…...
ESXi 重置密码详细攻略(全场景覆盖)
本文详细覆盖 ESXi 所有常见场景的密码重置方法,包括「知道原密码改新密码」「忘记root密码(无vCenter)」「有vCenter管理(企业版)」,步骤拆解到每一步点击和命令输入,适配 ESXi 5.x/6.x/7.x/8.x 全版本,兼顾官方支持方法和实用非…...
实战避坑:在Windows上用C++/WinRT搞定双模蓝牙(EDR+Ble)通信的完整流程
实战避坑:在Windows上用C/WinRT搞定双模蓝牙(EDRBle)通信的完整流程 蓝牙技术在现代设备中无处不在,但对于开发者而言,实现Windows桌面应用与双模蓝牙设备(同时支持经典蓝牙EDR和低功耗蓝牙BLE)…...
DeerFlow效果展示:自动生成的深度研究报告与播客内容惊艳分享
DeerFlow效果展示:自动生成的深度研究报告与播客内容惊艳分享 1. DeerFlow核心能力概览 DeerFlow作为一款深度研究智能助手,整合了语言模型、网络搜索和代码执行能力,能够自动完成从信息收集到内容生成的全流程工作。其核心功能亮点包括&am…...
Windows 10终极指南:免费开启HEIC缩略图预览功能
Windows 10终极指南:免费开启HEIC缩略图预览功能 【免费下载链接】windows-heic-thumbnails Enable Windows Explorer to display thumbnails for HEIC files 项目地址: https://gitcode.com/gh_mirrors/wi/windows-heic-thumbnails 还在为iPhone拍摄的照片在…...
毕业设计实战:基于SSM+JSP的家纺用品销售管理系统设计与实现全攻略
毕业设计实战:基于SSMJSP的家纺用品销售管理系统设计与实现全攻略 在开发“家纺用品销售管理系统”这套毕设时,我曾因“订单管理与商家库存脱节”踩过一个关键坑。初期设计时,我将“用户下单”和“商家库存扣减”视为两个独立操作,…...
益象创新与数谷智能,轻量化 AI 定制方案设计谁更优?
在企业数字化转型的下半场,人工智能(AI)的应用正从“大算力、大模型”的盲目崇拜,转向“轻量化、高适配”的务实落地上。对于中小型企业或大型企业的特定业务部门而言,动辄百万级的算力投入并不现实,一套能…...
WSL 启动闪退问题排查
第一步:检查当前状态在开始折腾 BIOS 之前,我们先确认一下系统到底有没有识别到虚拟化。按下快捷键 Ctrl Shift Esc 打开任务管理器。点击左侧的“性能”图标,选择 “CPU”。看右下角的信息,找到 “虚拟化”:如果是“…...
别再数据线了!用FastAPI 分钟搭个局域网文件+剪贴板神器
AI Agent 时代的沙箱需求 从 Copilot 到 Agent:执行能力的质变 在生成式 AI 的早期阶段,应用主要以“Copilot”形式存在,AI 仅作为辅助生成建议。然而,随着 AutoGPT、BabyAGI 以及 OpenAI Code Interpreter(现为 Advan…...
