76. 最小覆盖子串

题意：

解题思路：

思路：滑动窗口，双指针
1. 初始化T中字符次数，[a => 1, b => 1, c => 1]；
2. 初始化左右指针left right，移动right右窗口，以来找T中对应的字符；
3. 如果找到T中的所有字符，记录当前[left, right]长度；
4. 找到全部T，压缩左边窗口，即左滑窗口[0,4] => [1, 5]，
    继续移动右窗口，直到找到下一个满足全部T的窗口，继续缩小左边窗口；
5. 每一次找到全部T字符，记录下最小窗口范围，最后返回最短字符；

PHP代码实现：

class Solution {
    /**
     * @param String $s
     * @param String $t
     * @return String
     */
    function minWindow($s, $t) {        
        if (strlen($s) < strlen($t)) return '';
        $map = [];
        for ($i = 0; $i < strlen($t); $i++) ++$map[$t[$i]];
        $left = 0; $count = 0;
        $min = PHP_INT_MAX;
        for ($right = 0; $right < strlen($s); $right++) {
            if (isset($map[$s[$right]])) {
                //每个要找的值初始是1，找到后总数+1，是为了匹配strlen(s),得到长度
                if ($map[$s[$right]] > 0) $count++;//总数+1
                $map[$s[$right]]--;
            }
            while ($count == strlen($t)) {
                //找到之后记录长度
                if ($right - $left < $min) {
                    $min = $right - $left;
                    $head = $left;
                    $end = $right;
                }
                //只要找到全部T，就要压缩左边窗口，即左滑窗口[0,4] => [1, 5] => [1, 6]
                //首先左滑动窗口，去掉了一个值，就必须在后面元素找到这个值，才能使的长度匹配
                //1.总数count--，因为还要找一个【刚左滑动去掉的这个】
                //2.map+1,代表我们还要找一个left
                if (isset($map[$s[$left]])) {
                    if ($map[$s[$left]] >= 0) $count--;
                    //先加一
                    $map[$s[$left]]++;
                }
                //匹配之后，移动左边窗口，为了找到右侧最短长度；
                $left++;
            }
        }
        if ($min == PHP_INT_MAX) return '';
        return substr($s, $head, $end - $head + 1);
    }
}

GO代码实现：

func minWindow(s string, t string) string {
    mapT := make(map[byte]int)
    tlen, slen := len(t), len(s)
    for i := 0; i < tlen; i++ {
        mapT[t[i]]++
    }
    count, start, minlen, res := 0, 0, slen, ""
    for j := 0; j < slen; j++ {
        mapT[s[j]]--
        if  mapT[s[j]] >= 0 {
            count++
        }
        for count == tlen {
            if  minlen > j - start {
                minlen = j - start
                res = s[start:j+1]
            }
            mapT[s[start]]++
            if mapT[s[start]] > 0 {
                  count--
            }
            start++
        }
    }
    return res
}