12 最小覆盖子串 76

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

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

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