AcWing 799 双指针算法——最长连续不重复子序列

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

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

输入格式

第一行包含整数 n，第二行包含 n个整数（均在 0?105范围内），表示整数序列。

输出格式

共一行，包含一个整数，表示最长的不包含重复的数的连续区间的长度。
数据范围 1≤n≤105

输入样例：

5
1 2 2 3 5

输出样例：

3

解析：
双指针算法用来优化时间复杂度，本题利用双指针算法，将时间复杂度从O(n^2)优化成O(n)

双指针算法O(n)：

for(int i = 0, j = 0; i < n; i ++ )
{
    while(j <= i && check(i, j))res = max(res, i - j + 1);
}

朴素算法O(n^2)

for(int i = 0, i < n; i ++ )
{
    for(int j = 0; j < m; j ++ ){
    if(check(i, j))res = max(res, i - j + 1);}
}

初始状态：
i指针向后移动， 直到遇到重复出现的数字，(这个重复出现的数字一定是a[i]) 那么j指针开始向后移动，直到[j, i]区间内没有重复的数字。
具体判断是否重复出现是通过数组s[N]进行的记录。
开一个数组s[N], 当每次随着i指针的向后枚举，都执行一次s[a[i]] ++，当s[a[i]] > 1时，说明已经出现了重复出现的数字，这时，j指针开始移动，直到没有重复的数字为止。

代码实现如下：

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int a[N], s[N];
int n, res;
int main()
{
    cin >> n;for(int i = 0; i < n; i++ )cin >> a[i];for(int i = 0, j = 0; i < n; i++ ){
    s[a[i]] ++ ;while(s[a[i]] > 1){
    s[a[j]] -- ; //每当j指针向前移动一位，区间[j, i]内的元素就少一个，所以利用s[a[j]] -- 操作来使此数字弹出j ++ ;//代表j指针向后移动的操作;}res = max(res, i - j + 1 );}cout << res << endl;return 0;
}