Leetcode-in-JavaScript

# 滑动窗口算法

滑动窗口算法是一种常见的解决字符串或者数组问题的算法，其核心思想是维护一个窗口，通过窗口的变化来解决问题。其实就是一种利用首尾指针来维护一个区间的算法。

所谓滑动窗口，即指在遍历的数组中维护一个左闭右开区间的子数组，通过首尾指针来约定该子数组的范围。

常见题型描述为：比较字符串 s1 是否为字符串 s2 的某种子串排列。意思即为，只要 s2 中的某个窗口中恰好包含 s1 的所有字符，则满足题意。

# 算法思路

  1. 设置一个滑动窗口的 hash map，用于记录滑动窗口中的各字符数。

  2. 字符串遍历开始时，先将滑动窗口的左右边界索引都设置为 0，在遍历的过程中，先不断的扩充右边界，直到滑动窗口内的元素满足要求。

  3. 之后，我们将左边界不断缩小，并不断判断当前滑动窗口中的元素是否满足题目要求，若满足则更新结果。若不满足，停止缩小左边界。

  4. 然后不断重复上述过程，直到右边界达到数组尾。

  5. 注意，滑动窗口每变化一次，就要及时更新滑动窗口的匹配结果。

算法过程十分简单，甚至只需要考虑两个变量，便能通解所有滑动窗口的题型。

  1. 扩充右边界后，何时能使滑动窗口内的元素满足要求。从而可以开始缩小左边界。

  2. 何时更新返回结果。

# 代码模板

const window = {};
let res;
// 设计滑动窗口边界为左闭右开区间
let l = 0;
let r = 0;
while (l <= r && r < s.length) {
  // 更新滑动窗口中元素
  window[s[r]] = window[s[r]] ? window[s[r]] + 1 : 1;
  // 扩大右边界
  r += 1;

  //  1. 检查滑动窗口是否满足要求
  while (isValidWindow()) {
    // 2. 更新目标结果
    update(l, r, window);

    // 从左侧缩小滑动窗口
    window[s[l]] -= 1;
    l += 1;
  }
}
return res;

或者，一些题型下需要我们反向考虑，如果窗口不满足要求时缩小左侧窗口，直到满足要求，记录下来。

一般是用于求 最小值 / 最短范围 等类似的题型，代码模板如下：

while (l <= r && r < s.length) {
  // 更新滑动窗口中元素
  window[s[r]] = window[s[r]] ? window[s[r]] + 1 : 1;
  // 扩大右边界
  r += 1;

  //  1. 检查滑动窗口是否满足要求
  while (isValidWindow()) {
    // 从左侧缩小滑动窗口
    window[s[l]] -= 1;
    l += 1;
  }

  // 2. 更新目标结果
  update(l, r, window);
}

# 判断要点

由上面的代码模板可知，滑动窗口题型的大部分代码写法都是固定的，只有两处需要进行思考，分别是是否满足何时缩小窗口，以及如何更新目标结果。

其中判断何时缩小滑动窗口的判断条件是 isValidWindow() 函数。这个函数的具体实现需要根据题意来进行判断。一般来说，判断条件有以下几种：

  1. 如果是定长滑动窗口，判断条件为 r - l === k，即窗口内的元素个数等于 k。

  2. 如果是不定长，要求滑动窗口内的元素满足某些要求，则可以考虑使用一个 hash map 来记录窗口内的元素个数，然后判断是否满足要求。

至于第二部分，如何更新目标结果，update(res, xxx)。也有一些常见的解法：

例如一些题型，它求的是一个合法范围的数量，如满足要求的子串/集合个数等。这类题型大多使用上面的第二种模版。

面对窗口越大越合法的题型时，一般最后的 update 函数为 res += l。 这是因为满足题意的窗口为 [0,r], [1,r], [2,r], ..., [l,r]。共计 l 个。

面对窗口越小越合法的题型时，一般最后的 update 函数为 res += r - l + 1。这是因为满足题意的窗口为 [l,r], [l+1,r], [l+2, r], ..., [l,r]。共计 r - l + 1 个。

# 相关题型

  1. [3] 无重复字符的最长子串
  2. [76] 最小覆盖子串
  3. [438] 找到字符串中所有字母异位词
  4. [567] 字符串的排列
  5. [643] 子数组最大平均数 I

← 前缀和算法 →