滑动窗口相关题目

字符串、序列相关总感觉很麻烦，在考虑边界，递归的过程中，总是碍手碍脚的，感觉。
模版：双 while 循环

function test(s) {
    let n = s.length;
    let left = 0;
    let right = 0;
    while (right < n) {
        while(check()) { // 满足某个条件
            left++;
        }
        right++; // 不满足某个条件
    }
};

3. 无重复字符的最长子串

var lengthOfLongestSubstring = function(s) {
    let n = s.length;
    let map = new Map();
    let left = 0;
    let right = 0;
    let max = 0;
    while (right < n) {
        map.set(s[right], (map.get(s[right]) || 0) + 1);
        while(check(map)) { // 有重复
            let leftValue = s[left];
            map.set(leftValue, map.get(leftValue) - 1);
            left++;
        }
        // 无重复，计算最大长度的地方
        if (max < (right - left + 1)) {
            max = right - left + 1;
        }
        right++;
    }
    return max;
};
function check(map) {
    for (let [key, value] of map) {
        if (value > 1) {
            return true;
        }
    }
    return false;
}

76. 最小覆盖子串

精彩的题解（动画特别好）：
https://leetcode-cn.com/problems/minimum-window-substring/solution/shu-ju-jie-gou-he-suan-fa-hua-dong-chuan-p6ip/

var minWindow = function(s, t) {
    let n_s = s.length;
    let n_t = t.length;
    if (n_s < n_t) {
        return '';
    }
    let map_t = new Map(); // 连 map 都类似窗口
    for (let char of t) {
        map_t.set(char, (map_t.get(char) || 0) + 1);
    }
    let left = 0;
    let right = 0;
    let min = Infinity;
    let range = [left, right]
    while (right < n_s) { // 三个 while 循环，也真是 威武大气
        let curRight = s[right];
        if (map_t.has(curRight)) {
            map_t.set(curRight, map_t.get(curRight) - 1);
        }
        while (check(map_t)) { // 包含的话，一直减左边界
            let curLeft = s[left];
            if (map_t.has(curLeft)) { // 有才有的说
                map_t.set(curLeft, map_t.get(curLeft) + 1);
            }
            if (min > (right - left + 1)) { // 取到最小的表现
                min = right - left + 1;
                range = [left, right];
            }
            left++;
        }
        right++;
    }
    if (min === Infinity) { //没有找到合适的窗口： Infinity 可以比较，也真是学习到了
        return '';
    }
    return s.slice(range[0], range[1] + 1);
    function check(store) {
        for (let [key, value] of store) {
            if (value > 0) {
                return false;
            }
        }
        return true;
    }
};

209. 长度最小的子数组

和 76 题，基本上相同，代码结构都一样

var minSubArrayLen = function(target, nums) {
    let n = nums.length;
    let left = 0;
    let right = 0;
    let minLength = Infinity;
    while (right < n) {
        let curRight = nums[right];
        target = target - curRight;
        while (target <= 0) {
            if (minLength > (right - left + 1)) {
                minLength = right - left + 1;
            }
            let curLeft = nums[left];
            target = target + curLeft;
            left++;
        }
        right++;
    }
    if (minLength === Infinity) {
        return 0;
    }
    return minLength;
};

567. 字符串的排列

76 209 567 题目一样，代码结构都相同。

var checkInclusion = function(s1, s2) {
    let map_s1 = new Map();
    for (let char of s1) {
        map_s1.set(char, (map_s1.get(char) || 0) + 1);
    }
    let map = new Map();
    let left = 0;
    let right = 0;
    while (right < s2.length) {
        let curRight = s2[right];
        if (map_s1.has(curRight)) {
            map.set(curRight, (map.get(curRight) || 0) + 1);
        }
        while (check(map, map_s1)) {
            let curLeft = s2[left];
            if (right - left + 1 === s1.length) {
                return true;
            }
            if (map.has(curLeft)) {
                map.set(curLeft, map.get(curLeft) - 1);
            }
            left++;
        }
        right++;
    }
    function check (current, target) {
        for (let [key, value] of target) {
            if ((current.get(key) || 0) < value) {
                return false;
            }
        }
        return true;
    }
    return false;
};

219. 存在重复元素 II

固定窗口宽度，窗口内元素使用 set 存

var containsNearbyDuplicate = function(nums, k) { // 滑动窗口
    let n = nums.length;
    let set = new Set();
    for (let i = 0; i < n; i++) {
        let cur = nums[i];
        if (set.has(cur)) {
            return true;
        }
        set.add(nums[i]); // 现添加元素，然后再判断 set 是否超出容量
        if (set.size > k) {
            set.delete(nums[i - k]);
        }
    }
    return false;
};