Sliding Window

[campcc]

滑动窗口算法框架，

function slidingWindow(s, t) {
  // 利用哈希表（JavaScript 中可以用 Map 或空对象）记录目标字符串和窗口内字符串中字符的出现次数
  var need = {}, window = {};

  // 初始化哈希表，need 默认从 1 开始计数，window 默认从零开始计数
  for (var char of t) {
    need[char] = need[char] ? need[char] + 1 : 1;
    window[char] = window[char] ? window[char] + 1 : 0;
  }

  // 双指针记录滑动窗口的两端，size 记录窗口中满足 need 条件的字符的个数，然后开始滑动窗口
  var left = 0, right = 0, size = 0;
  while (right < s.length) {
    // c 是将移入窗口的字符
    var c = s[right];
    // 增大窗口
    right++;
    // 进行窗口内数据的一系列更新
    // ...

    // 判断左侧窗口是否需要收缩
    while (window needs shrink) {
      // d 是将移出窗口的字符
      var d = s[left];
      // 缩小窗口
      left--;
      // 进行窗口内数据的一系列更新
      // ...
    }
  }
}

比如力扣 76. 最小覆盖子串，我们可以直接套上面的框架，

function minWindow(s, t) {
    var need = {}, window = {}

    for (var char of t) {
        need[char] = need[char] ? need[char] + 1 : 1
        window[char] = window[char] ? window[char] + 1 : 0
    }

    var left = 0, right = 0, size = 0
    // 最小覆盖子串的起始索引和长度
    var start = 0, len = Infinity

    while (right < s.length) {
        var c = s[right]
        right++
        if (need.hasOwnProperty(c)) {
            window[c]++
            if (window[c] === need[c]) size++
        }

        // 判断左侧窗口是否需要收缩
        while (size === Object.keys(need).length) {
            if (right - left < len) {
                start = left
                len = right - left
            }
            var d = s[left]
            left++
            if (need.hasOwnProperty(d)) {
                if (window[d] === need[d]) size--
                window[d]--
            }
        }
    }

    return len === Infinity ? "" : s.substr(start, len)
};

再比如力扣 567. 字符串的排列，我们也可以直接套用框架，

function checkInclusion(s1, s2) {
    var need = {}, window = {}

    // 初始化哈希表，need = { a: 1, b: 1 }, window = { e: 0, i: 0, d: 0, b: 0, a: 0, o: 2 }
    for (var char of s1) {
        need[char] = need[char] ? need[char] + 1 : 1
        window[char] = window[char] ? window[char] + 1 : 0
    }

    // size 表示窗口中满足 need 条件的字符的个数
    // 比如对于窗口内的字符 a，need 中的出现次数为 1，当窗口中 a 出现次数也刚好为 1 时，我们把 size 加 1
    var left = 0, right = 0, size = 0

    while (right < s2.length) {
        var c = s2[right]
        right++
        // 增大窗口，更新当前元素出现的次数和 size
        if (need.hasOwnProperty(c)) {
            window[c]++
            if (window[c] === need[c]) size++
        }

        // 判断是否需要收缩左侧窗口
        // 什么时候需要收缩呢？题设要我们找的是排列，也就是当窗口长度刚好等于子串 s1 长度时，开始收缩
        while (right - left === s1.length) {
            // 收缩前先判断是否已经找到了子串
            if (size === Object.keys(need).length) {
                return true
            }
            var d = s2[left]
            left++
            if (need.hasOwnProperty(d)) {
                if (window[d] === need[d]) size--
                window[d]--
            }
        }
    }
    return false
};