双指针专题

滑动窗口

流程:

左指针右指针初始在同一位置,同方向移动,

每次检测左右指针之间的区域

不符合要求,右移右指针

符合要求则记录,右移左指针

跳出条件:右指针右移失败

需要关注的问题

问题描述

最大&条件:右移r到非法,记录此时长度为[l,r-1];然后右移l到合法

最小&条件:右移r到合法,右移l到非法,记录此时长度为[l,r]

lr之间的数据如何保存

set

3. 无重复字符的最长子串

map

340. 至多包含 K 个不同字符的最长子串

map+统计字母出现的数组(***)

76. 最小覆盖子串

前缀最值

辅助数组:lmax,rmax表示从最左(右)到该点的最大数字。

左指针=0右指针=n-1,初始在数组两边,反方向移动,

处理+移动,根据情况辨别谁先谁后

每次比较左右指针的数值大小+然后处理指向数值小的指针,根据其lmax,rmax等计算题设的值,必要时更新最值

11. 盛最多水的容器

每次计算此时的结果,根据结果判断哪个指针移动

18. 四数之和

跳出条件:两指针相遇

其他:

两个或以上指针指向需要标记的 index

75. 颜色分类

©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容