DT走过的路

描述

给出两个字符串 s 和 t，要求在 s 中找出最短的包含 t 中所有字符的连续子串。

数据范围：$0\le \mathrm{\mid }S\mathrm{\mid },\mathrm{\mid }T\mathrm{\mid }\le 10000$0≤∣S∣,∣T∣≤10000，保证s和t字符串中仅包含大小写英文字母

要求：进阶：空间复杂度 $O(n)$O(n) ， 时间复杂度 $O(n)$O(n)

例如：

$S=\mathrm{"}XDOYEZODEYXNZ\mathrm{"}$S="XDOYEZODEYXNZ"
$T=\mathrm{"}XYZ\mathrm{"}$T="XYZ"
找出的最短子串为$\mathrm{"}YXNZ\mathrm{"}$"YXNZ".

注意：
如果 s 中没有包含 t 中所有字符的子串，返回空字符串 “”；
满足条件的子串可能有很多，但是题目保证满足条件的最短的子串唯一。

示例1

输入：

"XDOYEZODEYXNZ","XYZ"

返回值：

"YXNZ"

示例2

输入：

"abcAbA","AA"

返回值：

"AbA"

思路

1. 记录需要的字符串，并统计数量，可能存在重复字符的可能；
2. 右指针朝右滑动，统计符合要求的字符数量，如果单个字符达到要求，valid++;
3. 当需求数量满足时，更新最小字符长度，并记录开始位置，
4. 通过移动left指针，缩小窗口，需要判断当前字符是否是需要字符，需要修改统计字符和valid.

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param S string字符串
 * @param T string字符串
 * @return string字符串
 */
function minWindow(S, T) {
       const need = new Map();
       for(ch of T){
         need.set(ch, (need.get(ch)||0)+1)
       }
       //console.log(need,'need')
       let left = 0;
       let right = 0;
       let valid = 0;
       let minLen = Infinity;
       let start = 0;
       const own = new Map();

        while(right < S.length){
            const cur = S[right];
            if(need.has(cur) ){
                own.set(cur,(own.get(cur)||0)+1);
                if(need.get(cur) === own.get(cur)){
                    valid++;
                }
            }
            right++;
            while(valid === need.size){
                //console.log(right-1,'right');
                const temp = S[left];
                if(right - left < minLen){
                    minLen = right - left;
                    start = left;
                }

                left++;
                if(need.has(temp)){
                    
                    if(need.get(temp) === own.get(temp)){
                        valid--;
                    }
                    //不能先减
                    own.set(temp,own.get(temp)-1);
                }

            }
        }
        return minLen === Infinity ? "" : S.slice(start,start + minLen);
    
}
module.exports = {
    minWindow: minWindow,
};

注意：

 if(need.get(temp) === own.get(temp)){
      valid--;
 }
//不能先减
own.set(temp,own.get(temp)-1);