双指针算法

学习双指针算法

双指针(Two pointers)有两大类

情况一: 两个指针指向两个不同的序列, 比如归并排序

情况二: 两个指针指向同一个序列, 这种出现的更多一些, 比如快排

一般的写法只有一种:

1
2
3
4
5
6
7
8
//一重循环, i 从 0开始, j 从某个点开始, 这里以 0 开始作为演示.  然后 i 把整个序列扫描一遍
for(int i = 0, j = 0; i < n; i++){
    //对于 j, 每次 i 更新完之后我们要更新我们的 j, 第一个判断条件是 j 的范围, 一定确保 j 在 合法范围 内,这里用 j<i 来演示. 
    //第二个条件就是满足某一个性质, 两个条件都满足, 则j++
    while(j < i && check(i,j)) j++;
    
    //题目本身的逻辑
}

解释: 让i把数组扫描一遍, j与i以某种性质维护一个区间

解题思路: 先用朴素算法O(N^2)来暴力解决问题, 然后看i j之间他们有没有单调关系, 有单调关系则利用单调关系套用模板把整个枚举的状态数量从N^2变为N

最长连续不重复子序列

判断子序列