76最小覆盖子串.md

双指针-滑动窗口

func minWindow(s string, t string) string {
    // 两个map来分别记录s和t的字符计数
    sMap, tMap := map[byte]int{}, map[byte]int{}
    for _, v := range []byte(t) {
        tMap[v]++
    }
    left, right, minLen := 0, -1, len(s) + 1
    // 定义方法来检查是否涵盖
    isValid := func() bool {
        for key, val := range tMap {
            if sMap[key] < val {
                return false
            }
        }
        return true
    }
    for i, j := 0, 0; j < len(s); j++ {
        sMap[s[j]]++
        for isValid() {
            if j - i + 1 < minLen {
                minLen = j - i + 1
                left, right = i, j
            }
            // 右移i减小窗口
            sMap[s[i]]--
            i++
        }
    }
    return s[left : right+1]
}