双指针算法

使用环境

1、两个指针法分别指向两个序列

2、两个指针维护一段区间

时间复杂度

O(n)

模板代码

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

最长连续不重复子序列题目链接

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

最长连续不重复子序列类型

双指针算法

最长连续不重复子序列朴素做法

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

最长连续不重复子序列代码

#include<iostream>

using namespace std;

const int N = 100010;

int n;
int a[N], s[N];

int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    int res = 0;
    for(int i=0,j=0;i<n;i++)
    {
        s[a[i]]++;
        while(s[a[i]]>1)
        {
            s[a[j]]--;
            j++;
        }
        res = max(res, i-j+1);
    }
    cout << res << endl;
    return 0;
}