双指针算法核心思想

原本两个指针是有 n2 种组合,因此时间复杂度是 O(n2) 。
而双指针算法就是运用单调性使得指针只能单向移动,因此总的时间复杂度只有 O(2n) ,也就是O(n)。

之所以双指针可以实现 O(n) 的时间复杂度是因为指针只能单向移动,没有指针的回溯,而且每一步都会有指针移动。

而朴素的 O(n2) 算法的问题就在于指针经常回溯到之前的位置

双指针算法的模板一般都可以写成下面的形式(模板):

1
2
3
4
5
6
7
for (int i = 0, j = 0; i < n; i++)
{
// check是满足某种性质
while (j < i && check(i, j)) j++;

// 每道题目的具体逻辑
}

799. 最长连续不重复子序列

给定一个长度为 n 的整数序列,请找出最长的不包含重复的数的连续区间,输出它的长度。

输入格式

第一行包含整数 n

第二行包含 n 个整数(均在 0 ~ 10^5 范围内),表示整数序列。

输出格式

共一行,包含一个整数,表示最长的不包含重复的数的连续区间的长度。

数据范围

1 ≤ n ≤ 10^5

输入样例:

1
2
5
1 2 2 3 5

输出样例:

1
3

暴力求解

  1. 无脑暴力求解(不作解释)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010;
int q[N];

int check(int l , int r ){
for(int i = l ; i <= r ; i++){
for(int j = l ; j < i ; j++){
if(q[i] == q[j]) return 0;
}
}
return 1;
}

int main()
{

int n;
cin >> n;

for (int i = 0; i < n; i ++ ) cin >> q[i];

int res = 0;
for (int i = 0; i < n; i ++ ){
for(int j = 0 ; j < i ; j++){
// 判断区间 [j,i] 是否有重复元素,没有重复元素就返回结果 check代表成功
if(check(j,i) == 1) res = max(res, i - j + 1);
}
}

cout << res << endl;

return 0;

}

这种会TLE。

双指针算法思想

可以考虑,使用i作为终点,j作为起点,让j去追赶i

ji在这个过程,如果是不同序列,那么就让i一直走。

如果遇到了重复序列,就让j去追赶i,直到这个重复序列结束,然后计算i - j + 1就是最长连续,但不重复的子序列长度

代码实现提示:对每个整数进行桶计数。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010;

int a[N], s[N];

int main(){

int n;
cin >> n;

for(int i = 0; i < n; i++) cin >> a[i];
// i和j下标最远距离
int res = 0;

for(int i = 0 , j = 0; i < n; i++){
// 对 a[i] 进行桶计数
s[a[i]]++;

// 跳过重复序列,s[a[i]]≥2的时候才可能触发,也就是进入了重复序列片段
while(s[a[i]] > 1){
// a[j]如果等于a[i]自然也就是剔除重复序列
s[a[j]]--;
j++;
}

// 只保留 i 和 j 相隔最远的距离。
// 即,最长连续,但不重复的子序列长度。
res = max(res, i - j + 1);
}

cout << res << endl;

return 0;
}