记一道算法题：最小覆盖子串-一一网

题目

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

注意：如果 s 中存在这样的子串，我们保证它是唯一的答案。

链接：leetcode-cn.com/problems/mi…

解题思路

1.先找出所有的包含T的子串

2.找出长度最小的子串，返回即可

解题步骤

1.用双指针维护一个滑动窗口，用来枚举出所有的子串
2.移动右指针，找到包含T的子串，移动左指针，尽量减少包含T的子串的长度
3.循环上述步骤，找出包含T的最小长度的子串

代码

/**
 * @param {string} s
 * @param {string} t
 * @return {string}
 */
var minWindow = function(s, t) {
    let l = 0;
    let r = 0;
    let res = '';
    //建一个字典用来表示需要的字符以及它的个数
    const need = new Map()
    for(let v of t){
        need.set(v,need.has(v) ? need.get(v) ++ : 1)
    }
    let needType = need.size
    //滑动窗口
    while(r < s.length){
        const c = s[r]
        //如果遍历到了需要的字符，那么需要的字符就要减少一个
        if(need.has(c)){
            need.set(c,need.get(c) - 1)
            //当需要的数量<=0,就证明把t遍历完了，此时移动左窗口
            if(need.get(c) === 0) needType -= 1
        }
        while(needType === 0) {
            const newArr = s.substring(l,r+1)
            if(!res || newArr.length < res.length) res = newArr
            const c2 = s[l]
            if(need.has(c2)){
                need.set(c2, need.get(c2) + 1)
                if(need.get(c2) === 1) needType += 1
            }
            l ++
        }
        r ++;
    }
    return res
};
复制代码