题解 | #最小覆盖子串#

看注释理解

题目：https://www.nowcoder.com/practice/c466d480d20c4c7c9d322d12ca7955ac

/**
  * 
  * @param S string字符串 
  * @param T string字符串 
  * @return string字符串
  */
function minWindow( S ,  T ) {
    // write code here
    const hash = new Map();
    for(let c of T)    hash.set(c, hash.get(c) + 1 || 1);	// 用于统计需要的字符数
    const targetLength = hash.size;
    const counts = new Map();	// 统计目前窗口中有效的字符数
    let l = 0;
    let res = '';
    let matchs = 0;
    for(let r = 0; r < S.length; r++) {
        if(hash.has(S[r])) {// 如果右指针指向元素是需要的
            counts.set(S[r], counts.get(S[r]) + 1 || 1);    // 在 counts 中增加数量
            if(counts.get(S[r]) === hash.get(S[r])) matchs++;    // 如果当前字符个数够了就增加匹配数
        }
        while(matchs === targetLength) {    // 满足匹配时不断增大左指针
            if(!res || res.length > (r - l + 1)) { // 保存结果
                res = S.slice(l, r + 1);
            }
            if(counts.has(S[l])) {    // 如果当前左指针指向元素在 counts 中
                counts.set(S[l], counts.get(S[l]) - 1);    // 发生计数元素删除操作
                if(counts.get(S[l]) < hash.get(S[l])) {  // 如果元素删除后导致元素个数'不够了'，减少匹配数
                    // 判断的依据是‘不够了’，而不是不相同，因为有可能 counts 中数量有多的
                    matchs--;    // 如果当前字符个数不够了，减少匹配数
                }
            }
            l++;    // 增大左指针
        }
    }
    return res;
}
module.exports = {
    minWindow : minWindow
};