滑动窗口小结

发表于 | 分类于

解题模板

这个算法技巧的思路非常简单，就是维护一个窗口，不断滑动，然后更新答案，困扰大家的，不是算法的思路，而是各种细节问题。比如说如何向窗口中添加新元素，如何缩小窗口，在窗口滑动的哪个阶段更新结果。

解题模板：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
let need = new Map()
  let window = new Map()
  for (let char of t) {
    if (need.has(char)) {
      need.set(char, need.get(char) + 1)
    } else {
      need.set(char, 1)
    }
  }

  let left = 0, right = 0
  let valid = 0 // 用于 window 包含 need 的多少个不重复数值，当 valid === need.size 时，则包含全部
  while (right < s.length) {
    let c = s[right] // c 是将移入窗口的数值
    right++ // 右移窗口
    // 进行窗口内数据的一系列更新
    // ...

    // debug 输出的位置
    console.log(left, right)

    // 判断左侧窗口是否要收缩
    while(valid === need.size) {
      let d = s[left] // d 是将移出窗口的字符
      left++ // 左移窗口
      // 进行窗口内数据的一系列更新
      // ...
    }
  }

然后开始套模板，只需要思考以下四个问题：

  1. 当移动 right 扩大窗口，即加入字符时，应该更新哪些数据？

  2. 什么条件下，窗口应该暂停扩大，开始移动 left 缩小窗口？

  3. 当移动 left 缩小窗口，即移出字符时，应该更新哪些数据？

  4. 我们要的结果应该在扩大窗口时还是缩小窗口时进行更新？

案例代码

典型直接套模板

76. 最小覆盖子串

滑动窗口算法的思路是这样：

  1. 我们在字符串 S 中使用双指针中的左右指针技巧，初始化 left = right = 0，把索引左闭右开区间 [left, right) 称为一个「窗口」。

  2. 我们先不断地增加 right 指针扩大窗口 [left, right)，直到窗口中的字符串符合要求（包含了 T 中的所有字符）。

  3. 此时，我们停止增加 right，转而不断增加 left 指针缩小窗口 [left, right)，直到窗口中的字符串不再符合要求（不包含 T 中的所有字符了）。同时，每次增加 left，我们都要更新一轮结果。

  4. 重复第 2 和第 3 步，直到 right 到达字符串 S 的尽头。

这个思路其实也不难，第 2 步相当于在寻找一个「可行解」，然后第 3 步在优化这个「可行解」，最终找到最优解，也就是最短的覆盖子串。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
var minWindow = function(s, t) {
  let need = new Map() // 用于记录需要凑齐的字符
  let window = new Map() // 用于记录当前窗口的字符
  for (let char of t) {
    if (need.has(char)) {
      need.set(char, need.get(char) + 1)
    } else {
      need.set(char, 1)
    }
  }

  let left = 0, right = 0
  let valid = 0 // 用于 window 包含 need 的多少个不重复数值，当 valid === need.size 时，则包含全部，满足题意
  // 记录最小覆盖子串的起始索引及长度
  let start = 0, len = Number.MAX_SAFE_INTEGER
  while (right < s.length) {
    let c = s[right] // c 是将移入窗口的数值
    right++ // 右移窗口
    // 进行窗口内数据的一系列更新
    if (need.has(c)) {
      if (window.has(c)) {
        window.set(c, window.get(c) + 1)
      } else {
        window.set(c, 1)
      }
      if (window.get(c) === need.get(c)) { // 满足了某个字符的所需个数
        valid++
      }
    }

    // 判断左侧窗口是否要收缩
    while(valid === need.size) {
      // 在这里更新最小覆盖子串
      if (right - left < len) {
        start = left
        len = right - left
      }
      let d = s[left] // d 是将移出窗口的字符
      left++ // 左移窗口
      // 进行窗口内数据的一系列更新
      if (need.has(d)) {
        if (window.get(d) === need.get(d)) {
          valid--
        }
        window.set(d, window.get(d) - 1)
      }
    }
  }
  // 返回最小覆盖子串
  return len === Number.MAX_SAFE_INTEGER ? '' : s.substr(start, len)
};

需要注意的是，当我们发现某个字符在 window 的数量满足了 need 的需要，就要更新 valid，表示有一个字符已经满足要求。而且，你能发现，两次对窗口内数据的更新操作是完全对称的。

当 valid == need.size() 时，说明 T 中所有字符已经被覆盖，已经得到一个可行的覆盖子串，现在应该开始收缩窗口了，以便得到「最小覆盖子串」。

移动 left 收缩窗口时，窗口内的字符都是可行解，所以应该在收缩窗口的阶段进行最小覆盖子串的更新，以便从可行解中找到长度最短的最终结果。

567. 字符串的排列

这题相当于: 相当给你一个 S 和一个 T，请问你 S 中是否存在一个子串，包含 T 中所有字符且不包含其他字符？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
/**
 * @param {string} s1
 * @param {string} s2
 * @return {boolean}
 * 滑动窗口
 * 相当给你一个 s1 和一个 s2，请问你 s2 中是否存在一个子串，包含 s1 中所有字符且不包含其他字符？
 */
var checkInclusion = function(s1, s2) {
  let need = new Map()
  let window = new Map()
  for (let char of s1) {
    if (need.has(char)) {
      let charNum = need.get(char) + 1
      need.set(char, charNum)
    } else {
      need.set(char, 1)
    }
  }

  let left = 0, right = 0
  let valid = 0 // 用于 window 包含 need 的多少个不重复数值，当 valid === need.size 时，则包含全部
  while (right < s2.length) {
    let c = s2[right] // c 是将移入窗口的数值
    right++ // 右移窗口
    // 进行窗口内数据的一系列更新
    if (need.has(c)) {
      if (window.has(c)) {
        let cNum = window.get(c) + 1
        window.set(c, cNum)
      } else {
        window.set(c, 1)
      }
      if (window.get(c) === need.get(c)) {
        valid++
      }
    }
    // debug 输出的位置
    // console.log(left, right)
	
    // 判断左侧窗口是否要收缩
	while (valid === need.size) {
      if (right - left === s1.length) {
        return true
      }
      let d = s2[left] // d 是将移出窗口的字符
      left++ // 左移窗口
      // 进行窗口内数据的一系列更新
      if (need.has(d)) {
        if (window.get(d) === need.get(d)) {
          valid--
        }
        window.set(d, window.get(d) - 1)
      }
    }
	/* 这题也可以先判断长度满不满足
    while(right - left >= s1.length) {
	  // 在判断是否包含整个字串
      if (valid === need.size) {
        return true
      }
      let d = s2[left] // d 是将移出窗口的字符
      left++ // 左移窗口
      // 进行窗口内数据的一系列更新
      if (need.has(d)) {
        if (window.get(d) === need.get(d)) {
          valid--
        }
        let dNum = window.get(d) - 1
        window.set(d, dNum)
      }
    }
	*/
  }
  return false
};

对于这道题的解法代码，基本上和最小覆盖子串一模一样，只需要改变两个地方：

  1. 本题移动 left 缩小窗口的时机是 valid == need.size() 时候，索命当 window 包含所有字串的字符

  2. 当发现长度和字串相同时，就说明窗口中就是一个合法的排列，所以立即返回 true。

至于如何处理窗口的扩大和缩小，和最小覆盖子串完全相同。

进阶多一些存储或其它操作

438. 找到字符串中所有字母异位词

所谓的字母异位词，就是排列，相当于：输入一个串 S，一个串 T，找到 S 中所有 T 的排列，返回它们的起始索引。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
/**
 * @param {string} s
 * @param {string} p
 * @return {number[]}
 */
var findAnagrams = function(s, p) {
  let need = new Map()
  let window = new Map()
  for (let char of p) {
    if (need.has(char)) {
      let charNum = need.get(char) + 1
      need.set(char, charNum)
    } else {
      need.set(char, 1)
    }
  }

  let left = 0, right = 0
  let valid = 0 // 用于 window 包含 need 的多少个不重复数值，当 valid === need.size 时，则包含全部
  let res = []
  while (right < s.length) {
    let c = s[right] // c 是将移入窗口的数值
    right++ // 右移窗口
    // 进行窗口内数据的一系列更新
    if (need.has(c)) {
      if (window.has(c)) {
        let cNum = window.get(c) + 1
        window.set(c, cNum)
      } else {
        window.set(c, 1)
      }
      if (window.get(c) === need.get(c)) {
        valid++
      }
    }
    // debug 输出的位置
    // console.log(left, right)

    // 判断左侧窗口是否要收缩
    while(right - left >= p.length) {
      if (valid === need.size) {
        res.push(left)
      }
      let d = s[left] // d 是将移出窗口的字符
      left++ // 左移窗口
      // 进行窗口内数据的一系列更新
      if (need.has(d)) {
        if (window.get(d) === need.get(d)) {
          valid--
        }
        let dNum = window.get(d) - 1
        window.set(d, dNum)
      }
    }
  }
  return res
};

跟寻找字符串的排列一样，只是找到一个合法异位词（排列）之后将起始索引加入 res 即可。

变异版

3. 无重复字符的最长子串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
  if (s.length < 2) {
    return s.length
  }
  let maxLen = 0
  let window = new Map()
  let left = 0, right = 0
  while (right < s.length) {
    let c = s[right]
    right++
    if (window.has(c)) {
      let cNum = window.get(c) + 1
      window.set(c, cNum)
    } else {
      window.set(c, 1)
    }
    while (window.get(c) > 1) { // 当发现重复项
      maxLen = window.size > maxLen ? window.size : maxLen
      let d = s[left]
      left++
      if (window.get(d) > 1) { 
        let dNum = window.get(d) - 1
        window.set(d, dNum)
      } else {
        window.delete(d)
      }
    }
    if (right === s.length) { // 处理迭代到最后一位
      maxLen = window.size > maxLen ? window.size : maxLen
    }
  }
  return maxLen
};

简单了，连 need 和 valid 都不需要，而且更新窗口内数据也只需要简单的更新计数器 window 即可。

当 window[c] 值大于 1 时，说明窗口中存在重复字符，不符合条件，就该移动 left 缩小窗口了嘛。

唯一需要注意的是，在哪里更新结果 maxLen 呢？我们要的是最长无重复子串，哪一个阶段可以保证窗口中的字符串是没有重复的呢？

这里和之前不一样，要在收缩窗口完成后更新 maxLen，因为窗口收缩的 while 条件是存在重复元素，换句话说收缩完成后一定保证窗口中没有重复嘛。

解题思路来自: labuladong的算法小抄