滑动窗口与双指针 | Typescript-Algorithms

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

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

「新」动计划 · 编程入门

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

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

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

一、定长滑动窗口

§1.1 基础

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

§1.2 进阶（选做）

§1.3 其他（选做）

二、不定长滑动窗口

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

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

§2.1 求最长/最大

§2.1.1 基础

§2.1.2 进阶（选做）

§2.2 求最短/最小

§2.3 求子数组个数

§2.3.1 越长越合法

一般要写 ans += left。

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

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

§2.3.2 越短越合法

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

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

思维扩展（选做）

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

§2.3.3 恰好型滑动窗口

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

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

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

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

注：也可以把问题变成 ≤k 减去 ≤k−1（两个至多）。可根据题目选择合适的变形方式。

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

§2.4 其他（选做）

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

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

三、单序列双指针

§3.1 相向双指针

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

§3.2 同向双指针

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

相似题目：

581. 最短无序连续子数组

§3.3 背向双指针

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

1793. 好子数组的最大分数 1946

§3.4 原地修改

思维扩展（选做）：

四、双序列双指针

§4.1 双指针

§4.2 判断子序列

进阶：

五、三指针

注：部分题目已整理到「§2.3.3 恰好型滑动窗口」中。

思维扩展：

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

六、分组循环

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

核心思想：

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

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

讲解

思考

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

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

关联题单

滑动窗口相关：数据结构题单中的「单调队列」。
双指针相关：贪心题单中的「单序列配对」和「双序列配对」。

算法题单

如何科学刷题？

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