碰碰战队|C++11题解系列-075 最小覆盖子串，leetcode( 二 )
下面来考虑用代码来实现 ， 先来回答一下前面埋下的伏笔 ， 为啥要用HashMap ， 而不是HashSet ， 现在应该很显而易见了吧 ， 因为要统计T串中字母的个数 ， 而不是仅仅看某个字母是否在T串中出现 。 统计好T串中字母的个数了之后 ， 开始遍历S串 ， 对于S中的每个遍历到的字母 ， 都在HashMap中的映射值减1 ， 如果减1后的映射值仍大于等于0 ， 说明当前遍历到的字母是T串中的字母 ， 使用一个计数器cnt ， 使其自增1 。 当cnt和T串字母个数相等时 ， 说明此时的窗口已经包含了T串中的所有字母 ， 此时更新一个minLen和结果res ， 这里的minLen是一个全局变量 ， 用来记录出现过的包含T串所有字母的最短的子串的长度 ， 结果res就是这个最短的子串 。 然后开始收缩左边界 ， 由于遍历的时候 ， 对映射值减了1 ， 所以此时去除字母的时候 ， 就要把减去的1加回来 ， 此时如果加1后的值大于0了 ， 说明此时少了一个T中的字母 ， 那么cnt值就要减1了 ， 然后移动左边界left 。 你可能会疑问 ， 对于不在T串中的字母的映射值也这么加呀减呀的 ， 真的大丈夫（带胶布）吗？其实没啥事 ， 因为对于不在T串中的字母 ， 减1后 ， 变-1 ， cnt不会增加 ， 之后收缩左边界的时候 ， 映射值加1后为0 ， cnt也不会减少 ， 所以并没有什么影响啦 ， 下面是具体的步骤啦：
【碰碰战队|C++11题解系列-075 最小覆盖子串，leetcode】-先扫描一遍T ， 把对应的字符及其出现的次数存到HashMap中 。
-然后开始遍历S ， 就把遍历到的字母对应的HashMap中的value减一 ， 如果减1后仍大于等于0 ， cnt自增1 。
-如果cnt等于T串长度时 ， 开始循环 ， 记录一个字串并更新最小字串值 。 然后将子窗口的左边界向右移 ， 如果某个移除掉的字母是T串中不可缺少的字母 ， 那么cnt自减1 ， 表示此时T串并没有完全匹配 。
推荐阅读
- 巅峰战队|VERTIX户外手表，勇攀新高峰——COROS
- 星球狂想战队|世界科技格局
- 家族战队|10年后退化成了“简陋版”，快看丨腾讯微博将于9月28日停服
- 路人战队|失去苹果的代价，有300万人承担不起，请别口嗨“抵制苹果”了
- 家族战队|就读懂了湖南互联网产业，读懂了这些话
- 路人战队|雷军用了什么法宝？，超越格力？新型洗烘一体机实现“弯道超车”
- 通天战队|别人偷动你手机，屏幕就会一戳一个洞，只有你可以打开，教你一招
- 碰碰战队|全面屏壁纸日常更新。9.3
- 家族战队|5G以后，通讯技术将帮你们讨回公道，长年被老公老婆忽悠的人们
- 路人战队|Longevity」，瞄准长寿抗衰老的生物技术，「励晶太平洋」宣布收购「Deep