一、是什么

学过计算机网络的同学，都知道滑动窗口协议，该协议是 TCP协议 的一种应用，用于网络数据传输时的流量控制，以避免拥塞的发生。该协议允许发送方在停止并等待确认前发送多个数据分组。由于发送方不必每发一个分组就停下来等待确认。因此该协议可以加速数据的传输，提高网络吞吐量。
滑动窗口算法其实和这个是一样的，只是用的地方场景不一样，可以根据需要调整窗口的大小，有时也可以是固定窗口大小。
简而言之，滑动窗口算法在一个特定大小的字符串或数组上进行操作，而不在整个字符串和数组上操作，这样就降低了问题的复杂度，从而也达到降低了循环的嵌套深度。
它通常适用以下几个情况：

  • 字符串、数组的局部操作，比如局部最小长度字符

    二、题目

    1、长度最小的子数组

    给定一个含有 n 个正整数的数组和一个正整数 target 。
    找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, …, numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。
    示例： :::info 输入: target = 7, nums = [2,3,1,2,4,3]
    输出: 2
    解释: 子数组 [4,3] 是该条件下的长度最小的连续子数组。 :::

    思路

    定义两个下标left 、right ，两者之间的子数组为滑动窗口。在更新窗口的过程中不断更新窗口之间的值和 sum.

  • 当 sum < target，说明值不够大，右边界右移

  • 当 sum >= target，满足条件，把当前窗口的大小和记录的最小值进行对比，更新最小值；并且 左边界右移，继续寻找最优解。

当 left 超过了数组的右边界，循环终止。

  1. var minSubArrayLen = function(target, nums) {
  2.     const len = nums.length
  3.     let res = Infinity
  4.     let sum = 0
  5.     // right取-1是为了计算元素和后，避免right越界后不能比较target和sum
  6.     let left = 0, right = -1
  8.     while (right < len) {
  9.         if (sum >= target) {
  10.            sum -= nums[left++]
  11.         } else {
  12.             sum += nums[++right]
  13.         }
  15.         if (sum >= target) {
  16.             res = Math.min(res, right - left + 1)
  17.         }
  18.     }
  19.     return res
  20. };

2、 无重复字符的最长子串

给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
示例1： :::info 输入: “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。 ::: 示例2： :::info 输入: “bbbbb”
输出: 1
解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。 :::

思路

首先我们定义一个左右边界left和right，形成窗口并保证该窗口无重复字符。
然后我们可以采用一个哈希表map去记录遍历的每一个字符的位置，若遇到重复字符，则更新位置。在此基础上解决重复字符的问题。

  • 左右滑动指针，左指针先不懂，右指针移动
  • 当右指针遇到重复字符时，将左指针更新到map中记录的位置+1
  • 右指针继续滑动

值得注意的是，遇到重复字符的时候，我们还需要判定重复字符的位置是否在left左边界的右边，从而避免left左边界的左边键值的影响。

  2. var lengthOfLongestSubstring = function(s) {
  3.     let len = s.length
  4.     let count = 0
  5.     if(!len) return count
  6.     let map = new Map()
  7.     let left = 0, right = 0
  9.     while(right < len) {
  10.         if(map.has(s[right]) && map.get(s[right]) >= left) {      
  11.             left = map.get(s[right]) + 1
  12.         }
  13.         count = Math.max(count, right - left + 1)
  14.         map.set(s[right], right)
  15.         right++
  16.     }
  17.     return count
  18. };

3、 最小覆盖子串

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 “” 。
示例 1： :::info 输入：s = “ADOBECODEBANC”, t = “ABC”
输出：”BANC” :::

思路

首先根据目标字符串t生成一个目标map，记录每个字符的目标值出现的次数，在遍历结束后利用变量mapSize记录map的长度
然后维护一个滑动窗口[left, right]，当右指针滑动到map中所存储的键值为 0 时，停止移动，此时表明所有t中字符已被覆盖。
滑动窗口的流程如下：

  • 右指针移动，当遇到t中字符，map中记录减一；
  • 当map中的记录元素的值为 0 时， mapSize减一；
  • 当mapSize为 0 时，表明此时t中所有字符都已被覆盖，记录当前子串；

  • 右滑左边界，若遇到map中存在的元素，计数加一.

    1. var minWindow = function(s, t) {
    2.   const sl = s.length, tl = t.length
    3.   let res = ''
    4.   if (tl > sl) return res
    5.   const map = new Map()
    6.   // 记录 t 中字符个数
    7.   for (let x of t) {
    8.       map.set(x, map.get(x)+1 || 1)
    9.   }
    11.   let left = 0, right = 0
    12.   let mapSize = map.size
    13.   while (right < sl) {
    14.       let x = s[right]
    15.       if (map.has(x)) {
    16.           map.set(x, map.get(x)-1)
    17.           if (map.get(x) === 0) mapSize--
    18.       }
    19.       while (mapSize === 0) {
    20.           const tmp = s.substring(left, right+1)
    21.           // 更新 长度更小的字符
    22.           if (!res || tmp.length < res.length) res = tmp
    24.           let c = s[left]
    25.           if (map.has(c)) {
    26.               map.set(c, map.get(c)+1)
    27.               if (map.get(c) === 1) mapSize++
    28.           }
    29.           left++
    30.       }
    31.       right++
    32.   }
    33.   return res
    34. };