zoomdong's blog
0%

滑动窗口解题技巧

Posted on

算法思想

  • 在字符串 S 中使用双指针的左右指针技巧，初始化 left = right = 0,索引闭区间 [left, right] 称为一个窗口
  • 先不断增加 right 指针扩大窗口 [left, right]，直到窗口中的字符串符合要求（包含了 T 中的所有字符串）
  • 此时，停止增加 right,转而不断增加 left 指针来缩小窗口 [left, right]，直到窗口中的字符串不再符合要求 (不包含 T 中的所有字符了)。同时，每次增加 left，都要更新一轮结果。
  • 重复 2 - 3 ,直到 right 到达尽头。

框架代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
string s, t;
int left = 0,right = 0;

string res = s;
while (right < s.size()) {
  window.add(s[right])
  right ++;
  // 如果符合要求，移动left缩小窗口
  while (window 符合要求) {
    // 如果这个窗口的子串更短，则更新res
    res = minLen(res, window);
    window.remove(s[left]);
    left++;
  }
}
return res;

那么我们要如何判断window即子串 s[left...right] 是否符合要求，是否包含 t 的所有字符呢？

可以用两个hash表来做计数器，一个记录t的字符以及出现次数，另一个window则记录当前窗口所包含的字符及出现的次数，如果window包含所有needs中的键，且这些键对应的值都大于等于needs中的值，那么就可以知道当前窗口符合要求了，可以开始移动left指针。

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
stirng s, t;
// 在s中找t的最小覆盖子串
int left = 0,right = 0;
string res = s;

// 相当于两个计数器
unordered_map<char, int> window;
unordered_map<char, int> needs;

for (char c : t) {
  needs[c] ++;
}

// 记录 window 中已经有多少字符符合要求了
int match = 0;

while (right < s.size()) {
  char c1 = s[right];
  if (needs.count(c1)) {
    // 加入window
    window[c1] ++;
    if (window[c1] === needs[c1]) {
      // 字符c1点出现符合次数了
      match ++;
    }
  }
  right ++;
  
  // window 中的字符已符合 needs 的要求了
  while (match === needs.size()) {
    // 更新结果res
    res = minLen(res, window);
    char c2 = s[left];
    if (needs.count(c2)) {
      // 移出 window
      window[c2] --;
      if (window[c2] < needs[c2]) {
        // 字符 c2 出现次数不再符合要求
        match --;
      }
    }
  }
}
return res;

lc76 最小覆盖子串

这题可以套一套我们上面的板子:

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
/**
 * @param {string} s
 * @param {string} t
 * @return {string}
 */
// s中能覆盖t的最小子串
// s = "ADOBECODEBANC",t = "ABC"
// res = "BNAC"
var minWindow = function (s, t) {
  s = s.split('')
  t = t.split('')
  let tMap = new Map()
  let window = new Map()
  let min = Number.MAX_SAFE_INTEGER
  let start = 0
  let l = 0,
    r = 0
  for (let i = 0; i < t.length; i++) {
    tMap.set(t[i], tMap.has(t[i]) ? tMap.get(t[i]) + 1 : 1)
  }
  let match = 0
  while (r < s.length) {
    let c1 = s[r]
    if (tMap.has(c1)) {
      window.set(c1, window.has(c1) ? window.get(c1) + 1 : 1)
      if (window.get(c1) === tMap.get(c1)) {
        match++
      }
    }
    r++
    // 如果window中的串已经符合要求了,开始移动左边，找符合条件的最小值
    while (match === tMap.size) {
      if (r - l < min) {
        start = l
        min = r - l
      }
      //  更新一下最短的字符串
      let c2 = s[l]
      if (tMap.has(c2)) {
        window.set(c2, window.get(c2) - 1)
        if (window.get(c2) < tMap.get(c2)) {
          match--
        }
      }
      l++
    }
  }
  return min === Number.MAX_SAFE_INTEGER ? '' : s.join('').slice(start, start + min)
}

// console.log(minWindow('ADOBECODEBANC', 'ABC'))