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

  |  

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

【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】
我的网站:潮汐朝夕的生活实验室
我的公众号:算法题刷刷
我的知乎:潮汐朝夕
我的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

Share