双指针算法核心思想

原本两个指针是有 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。

j与i在这个过程，如果是不同序列，那么就让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;
}