滑动窗口问题总结

一般可用于连续子序列，连续子字符串问题，这类问题暴力求解一般需要 \(O(N^2)\) 的复杂度，但是利用滑动窗口可以将复杂度降到 \(O(N)\)。

这类问题可以通过先扩张窗口，直到满足条件，再尽可能缩小窗口以得到最优解。如果题目不能通过这样的流程得到最优解，就要考虑别的解法了。

模板如下：

# 区间一般是左闭，右开，这样不容易写出Bug
l， r = 0， 0

while r < len(s):
    # 增大窗口
    window.add(s[r])
    r += 1
    
    # 尽可能地去缩小窗口
    while (l < r and window needs shrink):
        window.remove(s[l])
        left += 1
    
    # 判断是否需要更新答案

滑动窗口例题

76. Minimum Window Substring 3. Longest Substring Without Repeating Characters 438. Find All Anagrams in a String 567. Permutation in String

延伸 —— Rabin-Karp字符串匹配算法

187. Repeated DNA Sequences

ASCII本质是0-255的数字，那么匹配ASCII组成的字符串就变成了用滑动哈希算法计算字符串的hash再取mod，解决hash conflict了。

Reference： Labuladong Blog