滑动窗口
6/14/2022 滑动窗口
# 滑动窗口
滑动窗口是快慢指针的一种特殊形式，类似一个窗口一样移动。与快慢指针的一个区分点是，滑动窗口的左指针是依次移动，一般不存在跳跃式移动。
滑动窗口是对暴力解法的一种优化剪枝，一般能使时间复杂度优化到O(n)。
滑动窗口内容的题目一般分为四类：
- 定长，滑动窗口为固定长度
- 不定长度，滑动窗口为不定长长度
- 计数，使用滑动窗口解决计数类问题
- 数据结构，需要使用数据结构来维护窗口性质
对这四类问题再次细分，可以得到：
- 基础版，滑动窗口基础分为：定长和不定长两种形式，虽然不定长的写法可以包括定长，但是定长的写法效率更高点。
- 进阶版，滑动窗口进阶有两种类型：计数和数据结构。计数类问题主要解决窗口内计数相关问题（这里问题通常也可以用动态规划来解决）；有些问题需要对窗口使用特定的数据结构，比如堆、树等，即
滑动窗口+特定数据结构
这里强烈推荐完成 力扣 滑动窗口和双指针专题 (opens new window)，专题写的很不错，本文章为该专题的总结。
本文内容分为四个章节：