滑动哈希窗口

滑动窗口是一个特殊的双指针技巧,分别有左指针和右指针,在一个串上形成一个窗口。右指针向前移动窗口添加一个字符,左指针向前移动窗口删除一个字符。以此来判断窗口内的内容和模式串的内容是否相等。

我们建立一个哈希表,用来存储窗口内的内容

常见的代码结构如下

1
2
3
4
5
6
7
8
while(主串结束条件){
// r++
// 哈希表内添加字符
while(窗口满足条件){
// l++
// 哈希表减去一个字符
}
}