最小覆盖子串

滑动窗口算法的思路是这样：

• 1、我们在字符串 S 中使用双指针中的左右指针技巧，初始化 left = right = 0，把索引左闭右开区间 [left, right) 称为一个「窗口」。

• 2、我们先不断地增加 right 指针扩大窗口 [left, right)，直到窗口中的字符串符合要求（包含了 T 中的所有字符）。

• 3、此时，我们停止增加 right，转而不断增加 left 指针缩小窗口 [left, right)，直到窗口中的字符串不再符合要求（不包含 T 中的所有字符了）。同时，每次增加 left，我们都要更新一轮结果。

• 4、重复第 2 和第 3 步，直到 right 到达字符串 S 的尽头。

使用cntMap优化子串判断条件,统计每个子串需要出现的次数，以及需要几个不同的字母nums

时间复杂度：O(m+n),m,n分别为字符串m和n的长度

空间复杂度：O(n)

func getSubStr(s, t string) string {
    cntMap := make(map[byte]int, len(t))
    nums := 0
    for _, c := range []byte(t) {
        if cntMap[c] == 0 {
            nums++ // 统计t字符串中有几种字母出现
        }
        cntMap[c]++ //记录t字符串中每个字母需要出现的次数
    }

    ans1, ans2 := -1, len(s) //初始化最优解的左右窗口下标
    left := 0                //从[0,0]区间开始，右指针不断右移
    for right, c := range []byte(s) {
        cntMap[c]--         // 对应次数减1
        if cntMap[c] == 0 { //该字母满足出现次数要求
            nums-- //子串需要的字母总数减少一个
        }
        for nums == 0 { // 开始找最优解，直到子串字母需要出现的次数都满足，
            if right-left < ans2-ans1 { // 找到更短的子串
                ans1, ans2 = left, right // 记录此时的左右端点
            }
            x := s[left]        // 左端点字母
            if cntMap[x] == 0 { // x 移出窗口之前，检查出现次数，x字符移走后，次数要+1
                nums++
            }
            cntMap[x]++ // 左端点字母移出子串
            left++
        }
    }
    //左指针没有移动过，最大化窗口也不满足条件，没有找到
    if ans1 < 0 {
        return ""
    }
    return s[ans1 : ans2+1]
}