基本概念
滑动窗口是一种基于双指针的一种思想，两个指针指向的元素之间形成一个窗口。
应用：什么情况可以用滑动窗口来解决实际问题呢？
一般给出的数据结构是数组或者字符串
求取某个子串或者子序列最长最短等最值问题或者求某个目标值时
该问题本身可以通过暴力求解
窗口长度固定
| |
|
难度分 |
| |
【滑动窗口】【差分数组】C++算法：995K 连续位的最小翻转次数 |
1835 |
| 【C++滚动哈希 滑动窗口】2156. 查找给定哈希值的子串 |
1947 |
|
| 末端的部分窗口长度不足 |
【二分查找】【滑动窗口】LeeCode2528 最大化城市的最小电量 |
2235 |
| |
【滑动窗口】LeetCode2953:统计完全子字符串 |
2449 |
| |
【滑动窗口】LeetCode:30串联所有单词的子串 |
无 |
| |
【排序算法】【二叉树】【滑动窗口】LeetCode220: 存在重复元素 III |
无 |
| |
【map】【滑动窗口】【优先队列】LeetCode480滑动窗口中位数 |
无 |
| 预即2024年12月1号发布 |
难度分 |
| 【C++滑动窗口】1297. 子串的最大出现次数 |
1748 |
| 【C++滑动窗口】2653. 滑动子数组的美丽值 |
1785 |
| 【C++ 滑动窗口】2134. 最少交换次数来组合所有的 1 II |
|
不定长滑动窗口
令滑动窗口是nums[i…j-1]，一般分三步：
一，更新j。
二，处理。
三，更新i。
虽然是两层循环，但j不复位。故时间复杂度是：O(n)
| |
难度分 |
| 最长子数组 |
|
| 【C++二分查找 滑动窗口】2024. 考试的最大困扰度 |
1643 |
| 【C++二分查找 滑动窗口】2831. 找出最长等值子数组 |
1975 |
| 最长子数组2024年12月1号之前发布 |
|
| 【C++ 排序 滑动窗口】2779. 数组的最大美丽值 |
1638 |
| 【C++滑动窗口】1004. 最大连续1的个数 III |
1655 |
| 【C++单调队列】1438. 绝对差不超过限制的最长连续子数组 |
1672 |
| 【C++滑动窗口】2401. 最长优雅子数组 |
1749 |
| 【C++滑动窗口】1156. 单字符重复子串的最大长度 |
1787 |
| 【C++滑动窗口】2516. 每种字符至少取 K 个 |
1947 |
| 【C++滑动窗口 】2831. 找出最长等值子数组 |
1975 |
| 最短子数组预计2024年12月2号发布 |
|
| 【C++滑动窗口】1234. 替换子串得到平衡字符串 |
1877 |
| 【C++滑动窗口】2875. 无限数组的最短子数组 |
1913 |
| 【C++前后缀分解 双指针】1574. 删除最短的子数组使剩余数组有序 |
1932 |
| 统计子数组数量：越长越容易合法 预计2024年12月2号发布 |
|
| 【C++滑动窗口】1358包含所有三种字符的子字符串数目 |
1646 |
| 【C++滑动窗口】2962. 统计最大元素出现至少 K 次的子数组 |
1700 |
| 【C++滑动窗口】2537. 统计好子数组的数目 |
1891 |
| 统计子数组数量：越短越合法 预计2024年12月2号发布 |
|
| 二分查找前缀和滑动窗口2302:统计得分小于 K 的子数组数目 |
1808 |
| 【C++滑动窗口】2762. 不间断子数组 |
1940 |
| 统计子数组数量：恰好 预计2024年12月2号发布 |
|
| 【C++滑动窗口】1248. 统计「优美子数组」 |
1623 |
单系列双指针
枚举一个数组（系列、字符串）的两个子数组（一般是前缀和后缀）
| |
|
| 反向双指针2024年12月1号之前发布 |
|
| 【C++ 贪心 滑动窗口 前后缀分解】948. 令牌放置 |
1762 |
| 同向双指针 |
|
| 【C++ 滑动窗口】2122. 还原原数组 |
2158 |
双系列双指针
枚举两个数组（系列、字符串）的两个子数组（一般是前缀和后缀）
| 2024年12月5号之前发布 |
|
| 【C++算法：滑动窗口】809. 情感丰富的文字 |
1604 |
| 【C++滑动窗口】3132. 找出与数组相加的整数 II |
1620 |
| 【C++双指针】2337. 移动片段得到字符串 |
1693 |
| 【C++ 贪心】1616. 分割两个字符串得到回文串 |
1868 |
| 【双指针】【C++算法】1537. 最大得分 |
1961 |
三指针
枚举一个数组（系列、字符串）的两个子数组，这两个子数组共有一个端点。
| 2024年12月6号之前发布 |
|
| 枚举y，前缀、后缀 【C++双指针】825. 适龄的朋友 |
1697 |
| 共用左端点【C++ 三指针】2563. 统计公平数对的数目 |
1730 |
| 【C++ 三指针】795. 区间子数组个数 |
1817 |
| 【C++四指针】2444. 统计定界子数组的数目 |
2092 |
枚举子数组的两个边界，另一个边界不复位
由于不复位，所以时间复杂度是相加，而不是相乘。
| |
|
| |
二分查找 前缀和 滑动窗口 2302:统计得分小于 K 的子数组数目 |
| 有视频 |
二分查找 滑动窗口 前缀和 LeetCode209: 长度最小的子数组 |
| |
【滑动窗口】【map】LeetCode:76最小覆盖子串 |
| 两个滑动窗口 |
【滑动窗口】C++算法：K 个不同整数的子数组 |
| |
【滑动窗口】C++算法：可见点的最大数目 |
| |
【map】【滑动窗口】【字典树】C++算法：最长合法子字符串的长度 |
窗口的极值
| |
|
| 栈求区间极值是高频考点 |
【二叉树】【单调双向队列】LeetCode239:滑动窗口最大值 |
