LeetCode 76. 最小覆盖子串 【滑动窗口】
发布日期:2021-06-29 14:32:14
浏览次数:2
分类:技术文章
本文共 818 字,大约阅读时间需要 2 分钟。
题目描述
给定两个字符串 S 和T,求 S 中包含T 所有字符的最短连续子字符串的长度,同时要求时间 复杂度不得超过O(n)。
解题思路
需要思考以下四个问题:
1、当移动 right
扩大窗口,即加入字符时,应该更新哪些数据?
2、什么条件下,窗口应该暂停扩大,开始移动left
缩小窗口?
3、当移动 left
缩小窗口,即移出字符时,应该更新哪些数据?
4、我们要的结果应该在扩大窗口时还是缩小窗口时进行更新?
如果一个字符进入窗口,应该增加 window
计数器;如果一个字符将移出窗口的时候,应该减少 window
计数器;当 cnt
满足 need
时应该收缩窗口;应该在收缩窗口的时候更新最终结果。
需要注意的是,当我们发现某个字符在window
的数量满足了need
的需要,就要更新 valid,表示有一个字符已经满足要求。而且,你能发现,两次对窗口内数据的更新操作是完全对称的。
当 cnt == need.size()
时,说明T
中所有字符已经被覆盖,已经得到一个可行的覆盖子串,现在应该开始收缩窗口了,以便得到「最小覆盖子串」。
移动 left
收缩窗口时,窗口内的字符都是可行解,所以应该在收缩窗口的阶段进行最小覆盖子串的更新,以便从可行解中找到长度最短的最终结果。
AC
class Solution { public: string minWindow(string s, string t) { unordered_mapneed,window; for(char c : t) need[c]++; int left=0,right=0,cnt=0; // 记录最小覆盖子串的起始索引及长度 int start=0,len=INT_MAX; while(right
学如逆水行舟,不进则退
转载地址:https://chocolate.blog.csdn.net/article/details/105968276 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
能坚持,总会有不一样的收获!
[***.219.124.196]2024年04月16日 18时42分36秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
php如何将base64数据流文件转换为图片文件?
2019-04-29
JavaScript 的addEventListener() 事件监听详解!
2019-04-29
JavaScript的DOMContentLoaded事件和load的区别?
2019-04-29
PHP+JavaScript实现图片预览上传功能开发!
2019-04-29
JSONView - Chrome插件安装详解!(谷歌浏览器插件)!
2019-04-29
上传图片到阿里云OSS和获取上传图片的url的详解 !
2019-04-29
webstorm 和 phpstorm 有什么区别呢?做 WEB 开发用哪个好?
2019-04-29
常见位运算
2019-04-29
武大学生用python敲出樱花开放 | 附源码
2019-04-29
【中文教程】简单粗暴入门TensorFlow 2.0 | 北大学霸出品
2019-04-29
经典面试题:如何保证缓存与数据库的双写一致性?
2019-04-29
一份来自亚马逊工程师的Google面试指南,GitHub收获9.8万星,已翻译成中文
2019-04-29
硬货 | Redis 性能问题分析
2019-04-29
Kafka为什么这么快?
2019-04-29
灵魂四连问:API 接口应该如何设计?如何保证安全?如何签名?如何防重?
2019-04-29
一个依赖搞定 Spring Boot 反爬虫,防止接口盗刷!
2019-04-29
酸爽!IDEA 中这么玩 MyBatis,让编码速度飞起!
2019-04-29
已拿 Offer!字节跳动面试经验分享
2019-04-29
Windows路由表透析
2019-04-29
Java LockSupport 实战
2019-04-29