[算法]双指针 | 滑动窗口

经典滑动窗口

:::success

• [x] 1658. 将 x 减到 0 的最小操作数 :::

  倒序滑动窗口

  :::warning

• [x] 2156. 查找给定哈希值的子串 ::: [

](https://leetcode-cn.com/problems/minimum-operations-to-reduce-x-to-zero/)

字符串问题

剑指 Offer 48. 最长不含重复字符的子字符串

case 1: “abcabcbb” => 3
case 2: “bbbbb” => 1

滑动窗口+哈希表

var lengthOfLongestSubstring = function(s) {
    // 滑动窗口+哈希表
    // if (s.length < 2) return s.length;
    let left = 0;
    let hashTable = new Map();
    let res = 0;
    for (let right = 0; right < s.length; right++) {
        let cur = s.charAt(right)
        if (!hashTable.has(cur) || left > hashTable.get(cur)) {
            res = Math.max(res, right - left + 1)
        } else if (left <= hashTable.get(cur)) {
            left = hashTable.get(cur) + 1
        }
        hashTable.set(cur, right)
    }
    return res
};

76. 最小覆盖子串

辅助空间 （128是ASCII值总量， 实际97-122为存放a-z数量）

• need 标记目标字符
• window 标记滑动窗口中的字符

两层循环：

• 外侧负责右指针
  • 出口，指针移动至右边界
• 内侧负责左指针
  • 出口， 窗口包含目标字符

目标： 右指针右移扩大窗口
左指针右移缩小窗口
移动指针均对window产生影响

function minWindow(s: string, t: string): string {
    let n1 = s.length, n2 = t.length;
    if (n1 < n2) return '';
    let need = new Array(128).fill(0);
    let window = new Array(128).fill(0);
    for (let i = 0; i < n2; ++i) {
        ++need[t.charCodeAt(i)];
    }

    let left = 0, right = 0;
    let res = '';
    let count = 0;
    let min = n1 + 1;
    // 移动右指针
    while (right < n1) {
        let cur = s.charCodeAt(right);
        ++window[cur];
        if (need[cur] > 0 && need[cur] >= window[cur]) {
            ++count;
        }
        // 尽可能的移动左指针
        while (count == n2) {
            cur = s.charCodeAt(left);
            if (need[cur] > 0 && need[cur] >= window[cur]) {
                --count;
            }
            if (right - left + 1 < min) {
                min = right - left + 1;
                res = s.slice(left, right + 1);
            }
            --window[cur];
            ++left;
        }
        ++right;
    }
    return res;
};

接水问题

11. 盛最多水的容器

var maxArea = function(height) {
    let max = 0;
    let left = 0, right = height.length -1;
    while (left < right) {
        let area = (right - left) * Math.min(height[left], height[right]);
        max = Math.max(max, area);
        if (height[left] < height[right]) {
            left++;
        } else {
            right--;
        }
    }
    return max;
};

42. 接雨水 [字节]

左右指针+左右最大值

var trap = function(height) {
    let sum = 0;
    let left = 0, right = height.length - 1;
    let maxLeft = 0, maxRight = 0;
    while (left < right) {
        if (height[left] < height[right]) {
            // move left
            if (height[left] >= maxLeft) {
                maxLeft = height[left];
            } else {
                sum += maxLeft - height[left]
            }
            left++;
        } else {
            // move right
            if (height[right] >= maxRight) {
                maxRight = height[right];
            } else {
                sum += maxRight - height[right]
            }
            right--;
        }
    }
    return sum;
};