以数组为载体完成的任务中，有一类问题以「滑动窗口」为标签。这一类问题的思想其实并不复杂，但是在代码实现的时候，会有一些边界和细节的问题需要考虑。

对于绝大多数「滑动窗口」问题，一般而言，都需要先思考暴力解法，进而思考暴力解法是不是有可以优化的地方。
「暴力解法」通常以「二重循环」、「三重循环」的形式出现，优化的思路有：

  • 以空间换时间：在遍历的过程中，记录变量的值，以使得每一次不同规模的区间的相关信息的计算不必从头开始

  • 利用题目给出的性质，在枚举的过程中，能够一下子 排除很多不必要的方案 ，以降低时间复杂度

友情提示：滑动窗口的问题通常给我们的感觉是：这个问题并不难，但是我就是很难把它写对，应对这样的现象其实解决方案并不深奥，也是我们之前向大家多次提到过的：在程序出现问题的时候，一定不要忽视调试代码的作用。看一看我们在编写代码的过程中，是不是遵守了循环不变量，把这些变量的值打印出来看一下，或许问题就得到了解决。

「滑动窗口」算法的两个指针变量的移动方向是相同的，形成了一个「窗口」在直线上「滑动」的效果。我们以「力扣」第 3 题：无重复字符的最长子串为例进行讲解。

例题：「力扣」第 3 题：无重复字符的最长子串

这道题给我们一个字符串，要求我们找出这个字符串中不含有重复字符的 最长子串 的长度。首先我们需要弄清楚一个概念：「子串」，它通常区别于「子序列」。它们的区别是：

  • 子串（substring）：在原始数组中一定连续
  • 子序列（subsequeue）：在原始数组中不一定连续，只需要这些子序列中的元素保持在原始数组中的相对顺序

    方法一：暴力解法

    一个最直接的思考方案是：

枚举这个字符串的所有子串；
对于每一个子串都判断一下这个子串是否有重复字符；
在从没有重复字符的所有子串中找出长度最长的那个，返回即可。
部分代码如下：

  1. const lengthOfLongestSubstring = (s) => {
  2.     let len = s.length;
  3.   let maxLen = 1;
  4.   // 枚举到 len - 2 即可
  5.   for (let left = 0; left < len - 1; left++) {
  6.     for (let right = 0; right < len; right++) {
  7.       let subString = s.slice(left, right + 1);
  8.       // 如果 subString 不包含重复元素，记录 subString 的长度，并且维护 maxLen
  9.       // ... 代码省略
  10.     }
  11.   }
  12.   return maxLen;
  13. }

说明：首先看到一个二重循环，并且最里层的判断「subString 不包含重复元素」这个方法也是线性的。因此整体的复杂度是 O(N)

下面我们分析，是否有必要暴力枚举左右边界。在枚举的过程中，假设有如下中间状态：
image.png
image.png
image.png
image.png
image.png

  1. 一开始的时候，left与 right 重合，left 不动，right尝试向右边扩张，直到 [left, right] 中有恰有 1 个重复元素

  2. 如果在子区间 [left, right] 中有重复元素，[left, right + 1]、[left, right + 2] 一直到 [left, len - 1]一定包含重复元素，这一点是这问题可以使用「滑动窗口」的原因。此时就得考虑 left 向右移动，这是因为：

    1. left 不能向左移动：因为向左移动，仍然不能改变[left, right] 中有恰有 1 个重复元素的现状；
    2. left 只能向右移动，直到 left 刚刚好越过 right 指向的那个重复的元素为止。

  3. 接着有没有必要继续移动left 呢？答案是不可以，因为我们要求的是最长的子串的长度，此时的子串只是局部最长的。我们应该移动right以期待获得更长的不重复子串；

  4. 这样的过程一直进行下去，直到 right 到达字符串的末尾。

下面我们分析这个过程为什么比暴力枚举要快

  1. 当我们得到了一个有重复元素的子串的时候，和它 有相同前缀的所有子串 都会一下子被排除；
  2. 在判断子区间 [left, right] 是否有重复字符的时候，我们不必每一次都做扫描。事实上，我们只需要开辟一个字符频数数组，让右边界进来的时候，字符频数加 1，此时检测是否有重复。当左边界滑出的时候，字符频数减 1，此时检测是否无重复；
  3. 有重复字符的时候，尝试让左边界left右移，尝试让区间内无重复字符。没有重复字符的时候，尝试右边界 right 右移，以尝试让区间长度更长。

以上就是解决这道问题的基本思路。这种right主动向右移动，left 被动向右移动的方式就是滑动窗口的思想，也叫「尺取法」或者「虫取法」。这个名字可以说是非常形象了，一个资深的裁缝为我们量体裁衣，他很可能就是用右手大拇指在你的肩膀上做「滑动窗口」的样子。下面我们来看一下代码是如何编写的：

说明：编写代码的过程中遵守的 循环不变量 是：[left, right)内不包含重复字符。注意，这个区间是左闭右开的，好处是滑动窗口长度 = right - left。在一开始的时候，right 之前的元素已知，在本轮循环中，希望把 right 纳入，保持区间内无重复字符这一性质。

  1. /**
  2.  * @param {string} s
  3.  * @return {number}
  4.  */
  5. var lengthOfLongestSubstring = function(s) {
  6.   let len = s.length;
  7.   if(len < 2) {
  8.     return len;
  9.   }
  10.   const map = new Map();    // 存储元素出现次数
  11.   let res = 1;
  12.   for(let left = 0, right = 0; right < len; right++) {
  13.     map.set(s.charAt(right), ~~map.get(s.charAt(right)) + 1);
  14.     if(map.get(s.charAt(right)) == 2) {
  15.       while(map.get(s.charAt(right)) == 2) {
  16.         map.set(s.charAt(left), ~~map.get(s.charAt(left)) - 1);
  17.         left++;
  18.       }
  19.     }
  20.     res = Math.max(res, right - left + 1);
  21.   }
  22.   return res;
  23. };
  1. /**
  2.  * @param {string} s
  3.  * @return {number}
  4.  */
  5. var lengthOfLongestSubstring = function(s) {
  6.   let len = s.length;
  7.   if(len < 2) {
  8.     return len;
  9.   }
  10.   // 使用obj对象，代码更简洁一点，性能实际差不多
  11.   const map = {};
  12.   let res = 1;
  13.   for(let left = 0, right = 0; right < len; right++) {
  14.     if(!map[s.charAt(right)]) {
  15.       map[s.charAt(right)] = 1;
  16.     }
  17.     else {
  18.       map[s.charAt(right)] ++;
  19.     }
  20.     if(map[s.charAt(right)] == 2) {
  21.       while(map[s.charAt(right)] == 2) {
  22.         map[s.charAt(left)] --;
  23.         left++;
  24.       }
  25.     }
  26.     res = Math.max(res, right - left + 1);
  27.   }
  28.   return res;
  29. };

复杂度分析：

时间复杂度：O(N)，这里 N 是输入字符的长度，left 和 right 各扫过数组一次；
空间复杂度：O(M)，这里 M 表示字符出现的种类数。
说明：

  1. 创建字符频数数组，将字符的 ACSII 码作为数组的下标；
  2. 右边指针移动的过程中做加法：只要字符频数数组超过 11，刚刚好等于 22 的时候，就说明子区间内有重复元素；
  3. 左边指针移动的过程中做减法：因为我们的算法在子区间刚刚好有 11 个重复字符的时候，就想方设法让子区间没内有重复元素，因此重复元素的个数有且仅有 11 个，字符频数数组内单个字符的个数最多为 22，当左边界指向字符刚刚好减到 11 的时候，就说明子区间内没有重复元素（这样的说法有点绕，希望大家能够通过具体的例子，自己在纸上写写画画想明白）；
  4. 在右边指针移动的过程中记录最大值。要特别注意这里记录最大值的位置，不能在 if(map.get(s.charAt(right)) == 2) {之前，因为此时滑动窗口内可能有重复元素，因此，只能在if(map.get(s.charAt(right)) == 2) {之后。

滑动窗口的优化

仔细思考我们就会发现：一步一步来到重复元素出现过的地方太慢了，我们是不是可以一下子来到重复元素的后面呢？答案是：完全可以。具体的做法是：在遍历的过程中，不是记录元素的频数（其实在上一种做法里，频次最多也只用到 2），而是记录元素出现的位置。

当有重复元素出现的时候，只要这个元素之前出现的下标 大于等于 当前滑动窗口左边界的下标，就可以直接跳过来；如果重复元素之前出现的下标严格小于当前滑动窗口左边界的下标，左边界不用移动。

这两种情况，都需要更新当前看到的字符的下标为最新看到的字符的下标。

  2. /**
  3.  * @param {string} s
  4.  * @return {number}
  5.  */
  6. const lengthOfLongestSubstring = function (s) {
  7.   let window = {};
  8.   let left = 0;
  9.   let right = 0;
  10.   let res = 0;
  12.   while (right < s.length) {
  13.     let c = s[right];
  14.     // 扩大窗口是为了纳入所有的可行解决方案
  15.     window[c] = !window[c] ? 1 : window[c] + 1;
  16.     right++; 
  18.     // 有重复的,那就缩小窗口直到没有重复的
  19.     while (window[c] > 1) {
  20.       let d = s[left];
  21.       left++;
  22.       // 进行窗口内数据的一系列更新
  23.       window[d] = window[d] - 1;
  24.     }
  25.     res = Math.max(res, right - left);
  26.   }
  27.   return res;
  28. };

事实上，对于建立字符和某个数值的映射，也可以使用 哈希表 做。相信大家不难体会它们二者的差别。

这就是这一节的内容。下一节，我们再看一个使用「滑动窗口」解决的经典问题：「最小覆盖子串」，感谢大家。
image.png