LeetCode 76. 最小覆盖子串-526互联

题目链接：LeetCode 76. 最小覆盖子串

题意：

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。

解题思路：

方法：采用双指针的方法（或者叫滑动窗口）

双指针算法（滑动窗口）要满足单调性。即 i, j 指针均只能朝着一个方向移动, 不能一个指针向一个方向移动另一个指针向另一个方向移动.

1、滑动窗口 s[j ~ i], 设指针 i 为滑动窗口的终点, 指针 j 为滑动窗口的起点.

2、依次枚举每一个i,找出一个离i最近的j，使得从j到i 的这个子串是包含字符串t所有字符，（也就是对于每一个i，找到长度最小的包含 t 的所有字符的子串）

3、然后不断更新这个最小的子串

问题 1 ：如何快速判断滑动窗口 s[j ~ i] 内是否已经包含了 t内所有字符了呢(每种字符可能重复)？

首先使用哈希表ht来统计一下t里面每个字符出现的次数，哈希表hs来统计一下当前滑动窗口内每个字符出现的次数，

有效字符数量 cnt 表示当前窗口内，已经包含了多少个t里面的字符

滑动窗口内的有效字符总数量 cnt = len(t), 就说明已经包含了 t 内所有字符.
问题 2 ：那么什么是有效字符呢?
如果此时新加入了 s[i]字符之后, hw[s[i]] <= ht[s[i]], 此时的字符 s[i] 有用, 就算有效字符, cnt ++.

如果新加入了 s[i]字符之后, 有 hw[s[i]] > ht[s[i]] 了, 说明加入当前字符s[i] 之前, 滑动窗口内 s[i]的数量就已经达到了 t内这个字符s[i]的数量,

原本关于字符s[i] 就已经达标, 现在再加就是冗余, 就是无效字符.
问题 3 ：滑动窗口 s[j ~ i]的起点指针 j 什么时候才向右移动？
如果 s[j]处的字符 (字符记为#) 的数量大于 t 中这个字符 # 的数量, 即 hw[s[j]] > ht[s[j]],

j 就可以向右移动, 因为 s[j] 处的字符 # 的数量冗余了, j 向右移动的时候, 同时将 hw[s[j]] --
问题 4 : 有效字符的数量 cnt 变化是靠的什么呢？
cnt ++ 只能通过指针 i 向右移动, 但是注意指针 i 不一定每次向右移动都会使有效字符 cnt ++。

指针 j 向右移动不会影响有效字符cnt 的数量, 即虽然不会 cnt ++, 但是也不会出现导致cnt --.

完整代码如下：

func minWindow(s string, t string) string {

    hs := make(map[byte]int)  //表示当前窗口内，出现的字符的数量
    ht := make(map[byte]int) //表示t字符串中出现的所有字符的数量

    for i,_ := range t{   //统计t中，每个字符出现的次数
        ht[t[i]]++
    }
    var res string 
    count := 0   //记录当前的窗口中，有多少个有效的字符
    for i,j,n := 0,0,len(s);i < n;i++{  //j表示起点，i表示终点

        hs[s[i]]++
        if hs[s[i]] <= ht[s[i]] {   
            //对于窗口终点，如果当前窗口中，该字符出现的次数 不大于 t中出现的次数，说明当前窗口需要这个字符，因此，count++
            count++
        }

        for j < i && hs[s[j]] > ht[s[j]]  {   //对于窗口的起点，如果当前窗口中，该字符出现的次数 已经大于 t中出现的次数，说明当前窗口中这个字符已经多余了， hs[s[j]]--，同时起点向后移动 j++  
            //注意，这里是 for循环，因为可能起点会向后移动很多次，同时 这里一定要加上j < i这个条件，如果不加，会出现数组越界
            hs[s[j]]--
            j++
        }
        if count == len(t){//如果t中的所有字符都已经在窗口中，则筛选最小窗口
            if res == "" || (i-j+1) < len(res){
                res = s[j:i+1] 
            } 
        }
    }
    return res

}