分享丨【算法题单】滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）

灵茶山艾府

1440794

发布于未知归属地

双指针滑动窗口 C++Java Python Python3 周赛面试题数据结构数据结构与算法双周赛求职面试技术交流入门力扣竞赛

滑动窗口题单双指针题单力扣题目灵茶山艾府灵神灵神题单

如果你刚开始刷题，还不熟悉基本编程语法和常用库函数，推荐先刷力扣官方的入门题单：

「新」动计划 · 编程入门

有了一些简单题的积累，就可以开始刷我的题单啦~

下面的题目已按照难度分排序，右侧数字为难度分。

在刷题的过程中，如果遇到难度很大，题解都看不懂的题目，建议直接收藏，过段时间再来做。

一、定长滑动窗口

§1.1 基础

【套路】教你解决定长滑窗！适用于所有定长滑窗题目！

§1.2 进阶（选做）

思维扩展：

2200. 找出数组中的所有 K 近邻下标做到 $O (n)$
1461. 检查一个字符串是否包含所有长度为 K 的二进制子串 1504
1016. 子串能表示从 1 到 N 数字的二进制串做到 $O (∣ s ∣)$
2653. 滑动子数组的美丽值 1786

二、不定长滑动窗口

不定长滑动窗口主要分为三类：求最长子数组，求最短子数组，求子数组个数。

注：滑动窗口相当于在维护一个队列。右指针的移动可以视作入队，左指针的移动可以视作出队。

§2.1 越短越合法/求最长/最大

§2.1.1 基础

§2.1.2 进阶（选做）

§2.2 越长越合法/求最短/最小

§2.3 求子数组个数

§2.3.1 越短越合法

一般要写 ans += right - left + 1。

内层循环结束后， $[left, right]$ 这个子数组是满足题目要求的。由于子数组越短，越能满足题目要求，所以除了 $[left, right]$ ，还有 $[left + 1, right], [left + 2, right], \dots, [right, right]$ 都是满足要求的。也就是说，当右端点固定在 $right$ 时，左端点在 $left, left + 1, left + 2, \dots, right$ 的所有子数组都是满足要求的，这一共有 $right - left + 1$ 个。

思维扩展（选做）

3134. 找出唯一性数组的中位数 2451
3261. 统计满足 K 约束的子字符串数量 II 2659 子串的子串

§2.3.2 越长越合法

一般要写 ans += left。

内层循环结束后， $[left, right]$ 这个子数组是不满足题目要求的，但在退出循环之前的最后一轮循环， $[left - 1, right]$ 是满足题目要求的。由于子数组越长，越能满足题目要求，所以除了 $[left - 1, right]$ ，还有 $[left - 2, right], [left - 3, right], \dots, [0, right]$ 都是满足要求的。也就是说，当右端点固定在 $right$ 时，左端点在 $0, 1, 2, \dots, left - 1$ 的所有子数组都是满足要求的，这一共有 $left$ 个。

我们关注的是 $left - 1$ 的合法性，而不是 $left$ 。

1358. 包含所有三种字符的子字符串数目 1646
2962. 统计最大元素出现至少 K 次的子数组 1701
3325. 字符至少出现 K 次的子字符串 I 做到 $O (n)$
2062. 统计字符串中的元音子字符串做到 $O (n)$
2799. 统计完全子数组的数目做到 $O (n)$
2537. 统计好子数组的数目 1892
3298. 统计重新排列后包含另一个字符串的子字符串数目 II 1909 同 76 题
2495. 乘积为偶数的子数组数（会员题）

§2.3.3 恰好型滑动窗口

例如，要计算有多少个元素和恰好等于 $k$ 的子数组，可以把问题变成：

计算有多少个元素和 $\geq k$ 的子数组。
计算有多少个元素和 $> k$ ，也就是 $\geq k + 1$ 的子数组。

答案就是元素和 $\geq k$ 的子数组个数，减去元素和 $\geq k + 1$ 的子数组个数。这里把 $>$ 转换成 $\geq$ ，从而可以把滑窗逻辑封装成一个函数 $solve$ ，然后用 $solve (k) - solve (k + 1)$ 计算，无需编写两份滑窗代码。

总结：「恰好」可以拆分成两个「至少」，也就是两个「越长越合法」的滑窗问题。

注：也可以把问题变成 $\leq k$ 减去 $\leq k - 1$ ，即两个「至多」。可根据题目选择合适的变形方式。

注：也可以把两个滑动窗口合并起来，维护同一个右端点 $right$ 和两个左端点 $left_{1}$ 和 $left_{2}$ ，我把这种写法叫做三指针滑动窗口。

§2.4 其他（选做）

⚠ 滑窗的内容到这里就结束了，可以去刷下一个题单。

刷题路线请看如何科学刷题。

三、单序列双指针

§3.1 反转字符串

本质是相向双指针。

§3.2 相向双指针

两个指针 $left = 0, right = n - 1$ ，从数组的两端开始，向中间移动，这叫相向双指针。上面的滑动窗口相当于同向双指针。

思维扩展：

1861. 旋转盒子 1537
3814. 预算下的最大总容量 1796

§3.3 同向双指针

两个指针的移动方向相同（都向右，或者都向左）。

相似题目：

581. 最短无序连续子数组
3555. 排序每个滑动窗口中最小的子数组（会员题）

§3.4 背向双指针

两个指针从数组中的同一个位置出发，一个向左，另一个向右，背向移动。

1793. 好子数组的最大分数 1946
976. 三角形的最大周长思考题：改成最小周长（原题不是背向双指针，思考题是）

§3.5 原地修改

思维扩展：

§3.6 矩阵上的双指针

四、双序列双指针

§4.1 双指针

§4.2 判断子序列

进阶：

五、三指针

思维扩展：

3464. 正方形上的点之间的最大距离 2806 $k$ 个指针

六、分组循环

适用场景：按照题目要求，数组会被分割成若干组，每一组的判断/处理逻辑是相同的。

核心思想：

外层循环负责遍历组之前的准备工作（记录开始位置），和遍历组之后的统计工作（更新答案最大值）。
内层循环负责遍历组，找出这一组最远在哪结束。

这个写法的好处是，各个逻辑块分工明确，也不需要特判最后一组（易错点）。以我的经验，这个写法是所有写法中最不容易出 bug 的，推荐大家记住。

例题讲解

思考

做了一些题目后，请总结：滑动窗口和双指针的区别是什么？

欢迎在评论区发表你的做题总结。

关联题单

滑动窗口相关：
- 数据结构题单中的「单调队列」。
- 位运算题单中的「LogTrick」。部分题目可以用滑动窗口+栈解决。
双指针相关：
- 贪心题单中的「单序列配对」和「双序列配对」。

算法题单

如何科学刷题？

如果你发现有题目可以补充进来，欢迎评论反馈。