76.最小覆盖子串

let addMap = function (map, c) {
    if (!map.has(c)) {
        map.set(c, 1);
    } else {
        map.set(c, map.get(c) + 1);
    }
}
/**
 * @param {string} s 待匹配串
 * @param {string} t 子串
 * @return {string} 返回的字符串
 */
var minWindow = function (s, t) {
    let need = new Map();
    let window = new Map();
    let left = 0, right = 0;
    let valid = 0;
    let start = 0, len = Infinity;
    for (let c of t) {
        addMap(need, c);
    }
    while (right < s.length) {
        let c = s[right];
        right++;
        if (need.has(c)) {
            addMap(window, c);
            if (window.get(c) === need.get(c)) {
                valid++;
            }
        }
        while (valid === need.size) {
            if (right - left < len) {
                start = left;
                len = right - left;
            }
            let d = s[left];
            left++;
            if (need.has(d)) {
                if (window.get(d) === need.get(d)) {
                    valid--;
                }
                window.set(d, window.get(d) - 1);
            }
        }
    }
    return len === Infinity ? "" : s.substr(start, len);
};

18.最短超串

标准的滑动窗口模型

/**
 * @param {number[]} big
 * @param {number[]} small
 * @return {number[]}
 */
var shortestSeq = function (big, small) {
    const n = big.length;
    let res = [];
    let map = new Map();
    let minLen = n;
    // diff：记录滑动窗口一共需要覆盖的数字个数
    let diff = 0;
    // 数据预处理：统计需要覆盖的字符数量，放入到map中
    for (let e of small) {
        diff++;
        map.set(e, (map.get(e) || 0) + 1);
    }
    // 左指针和右指针初始化为0
    let left = 0, right = 0;
    while (right < n) {
        // 获取当前右坐标的数字
        const rightNum = big[right];
        if (map.has(rightNum)) {
            if (map.get(rightNum) > 0) {
                diff--;
            }
            map.set(rightNum, map.get(rightNum) - 1);
        }
        // 达到标准时候进行左坐标的处理
        while (diff === 0) {
            if (right - left < minLen) {
                minLen = right - left;
                res.push([left, right]);
            }
            // 获取当前左坐标的数字
            const leftNum = big[left];
            if (map.has(leftNum)) {
                map.set(leftNum, map.get(leftNum) + 1);
                if (map.get(leftNum) > 0) {
                    diff++;
                }
            }
            left++;
        }
        right++;
    }
    if (res.length) {
        return res[res.length - 1];
    } else {
        return [];
    }
};

567.字符串的排列

这个滑动窗口是一个变种，即窗口大小是固定的，左右同时移动

/**
 * @param {string} s1
 * @param {string} s2
 * @return {boolean}
 */
var checkInclusion = function (s1, s2) {
    let l = 0, r = s1.length - 1;
    let s1Map = new Map();
    for (let c of s1) {
        s1Map.set(c, (s1Map.get(c) || 0) + 1);
    }
    while (r < s2.length) {
        let map = new Map();
        for (let i = l; i <= r; i++) {
            const ch = s2[i];
            map.set(ch, (map.get(ch) || 0) + 1);
        }
        let res = cmpHash(s1Map, map);
        if (res === true) {
            return true;
        }
        l++;
        r++;
    }
    return false;

    /**
     * 比较是否重合
     * @param {Map} map1 参照哈希表
     * @param {Map} map2 需要判断的哈希表
     */
    function cmpHash(map1, map2) {
        for (let i of map1.keys()) {
            if (!map2.has(i)) {
                return false;
            } else if (map1.get(i) > map2.get(i)) {
                return false;
            }
        }
        return true;
    }
};

209.长度最小的子数组

/**
 * @param {number} target
 * @param {number[]} nums
 * @return {number}
 */
var minSubArrayLen = function (target, nums) {
    // 前缀和,[i,j)
    let sum = [];
    sum[0] = nums[0];
    const n = nums.length + 1;
    for (let i = 1; i < n; i++) {
        sum[i] = sum[i - 1] + nums[i - 1];
    }
    console.log(sum);
    let l = 0, r = 1;
    let minLen = Infinity;
    while (r < n) {
        let delta = sum[r] - sum[l];
        if (delta < target) {
            r++;
        }
        while (delta >= target) {
            if (r - l < minLen) {
                minLen = r - l;
            }
            console.log(l + ":" + r);
            l++;
            delta = sum[r] - sum[l];
        }
    }
    if (minLen === Infinity) {
        return 0;
    } else {
        return minLen;
    }
};