leetcode76-最小覆盖子串

leetcode 76

本题也是利用滑动窗口来解决，利用哈希表来记录t中每个字符的数量匹配，大于0表示缺少，小于0表示过剩，todo来记录总共还缺少的字母数量。
假设t = aabc，初始时t = 4,需要4个字母，map{a=>2,b=>1,c=>1}。如果匹配到了一个b，那么todo就要减少todo = 3，map{a=>2,b=>0,c=>1}，下次再匹配到b，此时todo不需要减少，因为b已经是0，也就是说b已经被覆盖了，当前需要的是a和c，所以todo不改变，因为map是记录在窗口内每个字母出现的频次，所以只要匹配到这个字符是t内的字符都要变更记录map{a=>2,b=>-1,c=>1}

var minWindow = function (s, t) {
    if(s.length < t.length) return "";
    let todo = t.length; // 记录还差多少个字母
    let map = frequencyMap(t);
    let slow = 0; // 左滑窗
    let result;
    for (let i = 0; i < s.length; i++) {
        const item = s[i];
        if (map.has(item)) { // 需要的字母
            if (map.get(item) > 0) { // 判断此字母是否还缺少
                todo--;
            }
            // 更新字母频次
            map.set(item, map.get(item) - 1);
            while (todo === 0) { // 覆盖所有子串，左窗口滑动缩小范围
                // 记录最小子串
                let ans = s.slice(slow, i + 1);
                if (!result || ans.length <= result.length) {
                    result = ans
                }
                if(map.has(s[slow])){
                    map.set(s[slow],map.get(s[slow])+1);
                    if(map.get(s[slow]) > 0){
                        todo++
                    }
                }
                slow++
            }
        }
    }
    return result || "";
};
// 记录每个字母需要出现的频数
function frequencyMap(s){
    const map = new Map();
    for (const item of s) {
        map.set(item, (map.get(item) || 0) + 1);
    }
    return map;
}