最小覆盖子串

最小覆盖子串 (opens new window)：

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

解题思路：

双指针寻找子串。从s的第一个字符串开始，移动右指针，直到当前双指针区域内的子串满足条件。然后移动左指针，每移动一次就查看是否还满足条件。当左指针移动到不满足条件的时候，又开始移动右指针重复上面的步骤。每一次移动指针满足条件后，都记录下当前子串及其长度方便比较。

var minWindow = function(s, t) {
    let needMap = {} // 记录需要的字符串的种类及其对应的数量
    for (const char of t) {
        needMap[char] = (needMap[char] || 0) + 1
    }
    let typeChar = Object.keys(needMap).length // 需要的字符的种类的数量，即有多少种字符
    let left = 0, right = 0, minLength = Infinity, minSubString = ""
    while (right < s.length) {
        const charRight = s[right]
        // 遍历到符合要求的元素，对应位置数量减一
        if (charRight in needMap) {
            needMap[charRight]--
            if (needMap[charRight] === 0) typeChar--
        }
        right++
        // 如果以及找齐了所有字母，开始尝试移动左指针
        while (typeChar === 0) {
            // 满足条件后，对比子串长度决定是否更新结果
            if (left - right < minLength) {
                minLength = right - left
                minSubString = s.slice(left, right)
            }
            const charLeft = s[left]
            // 移动左指针不满足条件时，针对needMap和typeChar变量更改，以便继续移动右指针
            if (charLeft in needMap) {
                needMap[charLeft]++
                if (needMap[charLeft] > 0) typeChar++
            }
            left++
        }
    }
    return minSubString
};