滑动窗口：你动我不动，我动你不动

长度最小的子数组

首先来看一道题：leetcode 209题长度最小的子数组： https://leetcode-cn.com/problems/minimum-size-subarray-sum

给定一个含有 n 个正整数的数组和一个正整数 target ，找出该数组中满足其和 ≥ target 的长度最小的连续子数组，并返回其长度。如果不存在符合条件的子数组，返回 0。

输入：target = 7, nums = [2,3,1,2,4,3] 输出：2   解释：子数组 [4,3] 是该条件下的长度最小的子数组。

首先，不考虑任何时间复杂度的情况下，用最简单的办法就是暴力遍历每一个子数组，将当前遍历到的子数组的长度以及子数组的和进行计算，若满足题目要求(子数组和大于等于target且长度最小)就更新结果长度。暴力解法的代码实现如下：

  // 思路1: 暴力解法 O(n^2)
  let res = nums.length + 1;
  let sum = 0;
  let subLens = 0;
  for(let i=0; i<nums.length; i++){
      sum = 0;
      for(let j=i; j<nums.length; j++){
          sum += nums[j];
          if(sum >= target){
              // 一旦当前子序列超过target就停止往后走并更新结果
              subLens = j - i + 1;    // 取子序列长度
              res = res > subLens ? subLens : res;
              break;
          }
      }
  }
  // 如果res还是原来的值说明没有符合条件的子序列
  return res === nums.length + 1 ? 0 : res;

滑动窗口算法思想

滑动窗口是类似双指针的一种算法解题思路，其特点如下：具备两个指针，一个指针(right)负责延展窗口，一个指针(left)负责收缩窗口。

滑动窗口的应用场景：

一般给出的数据结构是数组或者字符串
求取某个子串或者子序列最长最短等最值问题或者求某个目标值时
问题本身可通过暴力求解

滑动窗口的两个指针left和right的移动过程如下：

初始时，左右指针left,right都指向第0个元素，窗口为[left,right)，注意这里是左闭右开，因为初始窗口[0,0)区间没有元素
开始循环遍历整个数组元素，判断当前right指针是否超过整个数组的长度，是退出循环，否则执行第3步
然后right指针开始向右移动一个长度，并更新窗口内的区间数据
当窗口区间的数据满足我们的要求时，右指针right就保持不变，左指针left开始移动，直到移动到一个不再满足要求的区间时，left不再移动位置，在这个过程中会对题目要求的最长最短等要求进行判断对全局结果变量进行更新 => 核心步骤
执行第2步

上述移动过程可总结为下面的代码结构：

let left = 0;       // 滑动窗口起始位置(left)
let subLens = 0;    // 滑动窗口的长度
let start = -1;     // 窗口最后保存的开始位置

// 其他预处理: 比如求各个字符出现的次数
xxx 

for(let right=0; right<nums.length; right++){   // 滑动窗口结束位置(right)移动
  // 对nums[right]按题目要求进行处理,
  // 比如求和就是加起来, 求子串就是判断字符是不是目标字符, 是的话就把对应的字符个数加1
  xxx 
  while(窗口收缩的条件判断){
    if (right - left + 1 < subLens){
      start = left;                     // 更新窗口开始位置
      subLens = right - left + 1;       // 更新窗口长度
    }
    // 对要移除窗口的字符nums[left]按题目要求进行处理,
    // 比如求和就是减去, 求子串就是判断一下在不在, 在就把对应的字符个数减1
    xxx
    // 变更滑动窗口的起始位置
    left++
  }
}

// 最后返回结果
xxx

利用滑动窗口法实现长度最小的子数组的代码如下：

let minSubArrayLen = function (target, nums) {
  // 滑动窗口法 O(n)
  // 每个元素在滑动窗后进来操作一次，出去操作一次，每个元素都是被被操作两次，所以时间复杂度是 2 × n 也就是O(n)
  let res = nums.length + 1;
  let sum = 0;      // 滑动窗口的和
  let subLens = 0;  // 滑动窗口的长度
  let left = 0;     // 滑动窗口起始位置
  for(let right=0; right<nums.length; right++){   // 滑动窗口结束位置移动
    sum += nums[right];
    while(sum >= target){
      subLens = right - left + 1;
      res = subLens < res ? subLens : res;
      // 变更滑动窗口的起始位置
      sum = sum - nums[left++];
    }
  }

  // 如果res还是原来的值说明没有符合条件的子序列
  return res === nums.length + 1 ? 0 : res;
};

最小覆盖子串

leetcode 76题最小覆盖子串: https://leetcode-cn.com/problems/minimum-window-substring/ 给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。

输入：s = "ADOBECODEBANC", t = "ABC"   输出："BANC"
输入：s = "a", t = "a"    输出："a"
输入: s = "a", t = "aa"   输出: ""   
解释: t 中两个字符 'a' 均应包含在 s 的子串中，因此没有符合条件的子串，返回空串。

这个题也是用滑动窗口解决，只不过思路比上面那个稍微复杂一点，解决思路如下：首先统计t中的目标字符；然后用滑动窗口包含s的子串，当将移入窗口的字符是目标字符时将字符保存，如果当前字符在滑动窗口中出现的次数和t中出现的次数一样，验证数量加1；然后在收缩之前记录滑动窗口的开始位置并更新其长度，并对移除的字符进行如下判断：

是目标字符：判断当前字符的次数是否跟t中出现的次数相同，若相同将验证数量减1，然后将当前字符的次数减1，最后窗口左边界向右移动
不是目标字符：窗口左边界直接向右移动即可

这里面实现窗口收缩的判断是依据当前匹配的验证数量等于目标字符个数时，窗口中刚刚好包含了满足题目要求的字符串，但此时不一定是最小子串，因此需要进行基于窗口left左移实现的收缩，并在这个过程中对窗口的起始位置和窗口长度进行动态更新。

代码如下：

let minWindow = function (s, t) {
  // 特殊情况处理
  if (t.length > s.length) {
    return "";
  }

  // 思路: 滑动窗口
  let need = {};       // 目标串的字符-次数的键值对
  let window = {};     // 滑动窗口的字符-次数键值对
  for (let c of t) {
    // 统计需要的目标字符
    need[c] = (need[c] || 0) + 1;
  }

  let left = 0;
  let valid = 0;                    // 窗口中包含的字符个数
  let start = -1;                   // 窗口最后保存的开始位置
  let subLens = s.length + 1;       // 窗口长度
  for (let right = 0; right < s.length; right++) {
    let c = s[right]; // 将移入窗口的字符
    if (need[c]) {
      // 当前字符是需要的目标字符
      window[c] = (window[c] || 0) + 1;
      if (window[c] == need[c]) {
        // 当前窗口和需要的字符匹配时，验证数量增加1
        valid++;
      }
    }
    
    // 当验证数量与目标字符个数相等时说明应该收缩窗口了
    while (valid === Object.keys(need).length) {
      if (right - left + 1 < subLens) {
        start = left;   // 记录下开始位置以便最后计算出结果字符串
        subLens = right - left + 1;
      }
      // 即将移出的字符
      const outKey = s[left];
      // 判断移出的字符是否是目标字符
      if (need[outKey]) {
        if (window[outKey] === need[outKey]) {
          // 没有多余的情况下, 验证数量减少1
          valid--;
        }
        window[outKey]--;
      }
      // 窗口左边界右移
      left++;
    }
  }

  return start === -1 ? "" : s.slice(start, start + subLens);
};