题型总结: 滑动窗口 Sliding Window

发表于 | 分类于

基本思路

滑动窗口的问题可以解决一系列，有两个字符串，找一个字符串存在另一个字符串的某种性质的问题。
可以解决的问题参考同名tag. 这里只是列举一下模板

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
}
int SlidingWindow(String s, String p) {
  // 先建立一个map来存储p中的每一个字符出现的次数,etc
  Map<Character, Integer> map = new HashMap<>();
  for (char ch: p.toCharArray()) {
    map.put(ch, ...)
  }
  // 然后用两个左右指针，右指针遍历字符串s。同时需要维护一个变量count,
  // 这个变量的作用在于知晓需要找的性质是否找到之类的问题。
  int start = 0, end = 0, count = 0;
  while (end < s.length()) {
    char right = s.charAt(end);
    // 更新map中对应的数值, 同时需要更新count
    // count更新的条件取决于不同的题目。比如可以是所有的字符都出现过了。
    if (map.containsKey(right)) {
      // ...
      if (map.get(right) == 0) count--;
    }
    // 查看寻找的条件是否已达到
    while (count == 0) {
      // 更新要求的答案
      // 更新count
      start++;
    }  
    return res;
  }
}