赙浦 发表于 2025-5-30 14:23:57

12 最小覆盖子串 76

最小覆盖子串
又是一道硬题。
咱今天先把题干给读懂。

不定长滑窗
ADOBEC
DOBECODEBA
OBECDEBA
BECDEBA
ECDEBA
CDEBA
DEBANC
EBANC
BANC
ANC
我的思路是。
双指针，右指针不断向右滑动。
Q1.左指针什么时候动？
当右指针发现子串已经覆盖ABC（具体如何实现呢）时，左指针向右滑动，直到不能覆盖子串。
Q2.说得简单，如何知道子串有没有覆盖ABC呢？
可以把数组当做哈希表，26个字母对应26个下标，碰到了哪个字符就让哪个字符+1。
难道说右指针每次移动都要遍历一遍这个哈希表，看看是否满足条件吗？
这样时间复杂度是O(n^2)啊。
脑子崩了。

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！

诸婉丽 发表于 2025-11-14 08:40:54

热心回复！

赏听然 发表于 2025-11-21 17:40:40

热心回复！

岭猿 发表于 2025-11-23 13:32:16

鼓励转贴优秀软件安全工具和文档！

哈妙思 发表于 2025-12-15 08:33:43

yyds。多谢分享

蒲善思 发表于 2025-12-26 04:56:37

谢谢楼主提供！

师佳思 发表于 2026-1-7 23:44:41

感谢发布原创作品，程序园因你更精彩

少屠 发表于 2026-1-13 17:10:35

感谢分享，学习下。

史穹逊 发表于 2026-1-15 00:57:44

谢谢楼主提供！

懵诬哇 发表于 2026-1-18 02:10:49

懂技术并乐意极积无私分享的人越来越少。珍惜

琉艺戕 发表于 2026-1-18 15:11:09

喜欢鼓捣这些软件，现在用得少，谢谢分享！

利怡悦 发表于 2026-1-18 19:11:25

yyds。多谢分享

肇默步 发表于 2026-1-19 06:03:09

这个有用。

劳暄美 发表于 2026-1-20 10:55:57

yyds。多谢分享

僭墙覆 发表于 2026-1-21 01:58:18

感谢发布原创作品，程序园因你更精彩

左丘雅秀 发表于 2026-1-25 07:57:26

东西不错很实用谢谢分享

遑盲 发表于 2026-1-25 11:08:48

谢谢分享，辛苦了

骂治并 发表于 2026-1-26 12:25:16

这个好，看起来很实用

闵雇 发表于 2026-2-1 03:17:22

谢谢楼主提供！

仰翡邸 发表于 2026-2-4 13:46:31

鼓励转贴优秀软件安全工具和文档！
页: [1] 2 3
查看完整版本: 12 最小覆盖子串 76