尺取法(单串单向双指针)

摘要: 本文系统梳理了单串单向双指针的题目。

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

---

在文章 双指针 中，我们系统梳理了常见的双指针问题类型，包括单串单向、单串双向、双串单向、单串三指针等。

单串单向双指针的问题，有维护 [l, r] 和 [0, l] 两个常见的大类。对于维护 [l, r] 的问题，经常也称为尺取法，本文系统梳理尺取法的题目。

尺取法经常也称为不定长滑动窗口，如果区间长度是固定的，称为定长滑动窗口，这也是一大类问题，参考 滑动窗口。

$1 尺取法算法要点

• 在迭代过程中，推进 l 或 r 的方式是否明确
• 推进 l 和 r 的时机
• 推进 l 和 r 的方式
• 更新答案的时机
• 退出的时机

$2 题目

题目	问题类型	窗口数据特点	辅助数据结构	题解/备注
3. 无重复字符的最长子串	最长子串	不含重复字符	bitset	bitset
30. 串联所有单词的子串	所有符合的子串	词典所有词的拼接	哈希表	—
76. 最小覆盖子串	最短子串	字符计数包围另一串t	哈希表	—
159. 至多包含两个不同字符的最长子串	最长子串	至多两个不同字符	无
424. 替换后的最长重复字符	最长子串	含重复字母,可以替换k次	哈希表	题解
487. 最大连续1的个数 II	最长子串	连续1, 可以替换1次	无
532. 数组中的 k-diff 数对	子串数目	端点值差的绝对值为 k	无
467. 环绕字符串中唯一的子字符串	子串数目	为另一串p的非空子串	无
713. 乘积小于K的子数组	子数组数目	乘积小于k	无
845. 数组中的最长山脉	最长子数组	山脉数组	无
904. 水果成篮	最长子数组	最多两种不同数字	无
992. K 个不同整数的子数组	子数组数目	K 中不同数字	哈希表
795. 区间子数组个数	子数组数目	最大元素在 [L, r] 之间	无	—
395. 至少有K个重复字符的最长子串	最长子串	每个字符出现次数均>=k	哈希表	题解
1004. 最大连续1的个数 III	最长子数组	连续1,最多替换k次	无
1234. 替换子串得到平衡字符串	最短子串	给定字符限定最少次数	哈希表
1358. 包含所有三种字符的子字符串数目	子串数目	给定字符限定最少次数	哈希表
面试题 17.18. 最短超串	最短子数组	字符计数包围另一数组	哈希表
340. 至多包含 K 个不同字符的最长子串	最长子串	至多k个不同字符	哈希表
209. 长度最小的子数组	最短子数组	和 >= s	无
727. 最小窗口子序列	最短子串	另一串 t 为其子序列	无
1208. 尽可能使字符串相等	最长子串	转换为另一串t的成本 <= k	无
1100. 长度为 K 的无重复字符子串	子串数目	无重复字符	bitset

---