经典150题 - 滑动窗口

209. 长度最小的子数组

var minSubArrayLen = function(target, nums) {
    let left = 0;
    let sum = 0;
    let minLen = Infinity; // 先设为一个无穷大，便于后续取最小值
 
    for (let right = 0; right < nums.length; right++) {
        sum += nums[right]; // 扩大窗口，加入右侧元素
 
        // 当窗口内的和大于等于 target 时，尝试缩小窗口
        while (sum >= target) {
            minLen = Math.min(minLen, right - left + 1); // 更新最小长度
            sum -= nums[left]; // 移出左侧元素
            left++;            // 左指针右移
        }
    }
 
    // 如果 minLen 还是 Infinity，说明没有找到符合条件的子数组，返回 0
    return minLen === Infinity ? 0 : minLen;
};

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

var lengthOfLongestSubstring = function (s) {
    let left = 0
    let max = 0 // 初始化为 0 更好，处理空字符串
    let set = new Set()
 
    for (let right = 0; right < s.length; right++) {
        // 使用 while 循环，把左边直到重复字符为止的所有字符都删掉
        while (set.has(s[right])) {
            set.delete(s[left])
            left++
        }
        
        set.add(s[right])
        max = Math.max(max, right - left + 1)
    }
    
    return max
};

76. 最小覆盖子串

if (s.length < t.length) return "";
 
    let map = new Map();
    for (let char of t) {
        map.set(char, (map.get(char) || 0) + 1);
    }
 
    let l = 0, r = 0;
    let need = map.size; // 缺少的字符种类数
    let start = 0;
    let minLen = Infinity;
 
    while (r < s.length) {
        let c = s[r];
        if (map.has(c)) {
            map.set(c, map.get(c) - 1);
            // 当某字符的需求量减到 0，说明该字符在窗口内的数量已经达标
            if (map.get(c) === 0) {
                need--;
            }
        }
 
        // 当所有字符种类都达标了，尝试收缩左窗口
        while (need === 0) {
            // 更新最小覆盖子串的长度和起始位置
            if (r - l + 1 < minLen) {
                start = l;
                minLen = r - l + 1;
            }
 
            let c2 = s[l];
            if (map.has(c2)) {
                // 如果本来是 0，说明刚好达标，移出后就不达标了
                if (map.get(c2) === 0) {
                    need++;
                }
                map.set(c2, map.get(c2) + 1);
            }
            l++; // 左指针右移
        }
        r++; // 右指针右移
    }
 
    return minLen === Infinity ? "" : s.slice(start, start + minLen);

相关笔记

• 双指针
• 哈希表（最小覆盖子串）
• GRD 字符串刷题