滑动窗口

发表于2024-04-22更新于2024-04-26

滑动窗口

算法题应用场景

满足***条件的（计算结果、出现次数），包含最长/最短 子串/子数组/子序列

滑动窗口的思路

图 0

滑动窗口模板

1
2
3
4
5
6
7
8
9
10
// 找最长的模板
// 初始化left，right，result，bestresult
while(右指针到达结尾处){
  窗口逐渐扩大，加入right对应元素，更新result
  while(result不满足要求){
    窗口缩小、移除left对应元素，left右移
  }
  更新最优结果bestresult
  right++
}
1
2
3
4
5
6
7
8
9
10
// 找最短模板
// 初始化left，right，result，bestresult
while(右指针到达结尾处){
  窗口扩大，加入right对应元素，更新result
  while(result满足条件){
    更新最优结果bestresult
    窗口缩小，移除left对应元素，left右移
  }
  right++
}

题目

无重复字符串的子串

https://leetcode.cn/problems/longest-substring-without-repeating-characters/description/

重点在于如何判断无重复字符串

判断是否有重复字符串,使用字典map和调整left位置实现无重复子串。

图 3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
var lengthOfLongestSubstring = function(s) {
  // 初始化
  let p=0;q=0;max=0;
  let map = new Map();
  // 右指针逐渐向结尾处移动
  while(q<s.length){
    // 当结果不满足条件
    if(map.has(s[q])){
      p = Math.max(map.get(s[q])+1,p)
    }
    map.set(s[q],q);
    max = Math.max(max,q-p+1);
    q++;
  }
}

串联所有单词的子串

https://leetcode.cn/problems/substring-with-concatenation-of-all-words/description/

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
var findSubstring = function(s, words) {
  let res = []
  let wordLen = words[0].length
  let wordNum = words.length
  let wordMap = new Map()
  for (let word of words) {
    wordMap.set(word, wordMap.has(word) ? wordMap.get(word) + 1 : 1)
  }
  // 这里i的设置比较难理解，但是如果理解了后面while中的逻辑，就懂了
  // 从i开始，right直接到最后可能的位置，也就是for中的一次遍历可以找到0或多个res，而不是1个
  for (let i = 0; i < wordLen; i++){
    let left = i
    let right = i
    let window = new Map()
    let count = 0
    while (right + wordLen <= s.length) {
      let w = s.slice(right, right + wordLen)
      right += wordLen
      if (!wordMap.has(w)) {
        window.clear()
        count = 0
        left = right
      } else {
        window.set(w, window.has(w) ? window.get(w) + 1 : 1)
        count++
        while (window.get(w) > wordMap.get(w)) {
          let l = s.slice(left, left + wordLen)
          left += wordLen
          window.set(l, window.get(l) - 1)
          count--
        }
        if (count === wordNum) {
          res.push(left)
        }
      }
    }
  }
  return res
}
Text
1
2
3
4
5
6
7
8
9
10
11
12
13
这段代码的主要逻辑是使用滑动窗口来遍历字符串 s，并检查每个窗口是否包含 words 中的所有单词。

1、let left = i 和 let right = i：初始化滑动窗口的左右边界。
2、let window = new Map()：创建一个哈希映射 window 来存储当前窗口中每个单词出现的次。
3、let count = 0：初始化一个计数器 count 来存储当前窗口中的单词总数。
4、while (right + wordLen <= s.length)：当窗口的右边界加上单词的长度不超过字符串 s 的长度时，继续循环。
5、let w = s.slice(right, right + wordLen)：获取窗口右边界的单词 w。
6、right += wordLen：将窗口的右边界向右移动一个单词的长度。
7、if (!wordMap.has(w))：如果 w 不在 wordMap 中，那么清空 window，重置 count，并将窗口的左边界移动到 right。
8、else：如果 w 在 wordMap 中，那么更新 window 和 count，并检查 window 中 w 的数量是否超过了 wordMap 中 w 的数量。如果超过了，那么从窗口的左边移除单词，直到 window 中 w 的数量不超过 wordMap 中 w 的数量。
9、if (count === wordNum)：如果 count 等于 wordNum，那么将窗口的左边界添加到结果数组 res 中。

这个滑动窗口的策略确保了我们能够有效地遍历字符串 s，并找出所有包含 words 中所有单词的子串的起始索引。