算法

双指针算法

板子

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

    //后面+每道题的逻辑
}

a数组存输入的样例, s数组当前维持的区间内下标的数字出现的个数。
这道题中, check(i, j) 是 s[a[i]] > 1 。s[a[i]]表示当前维持的这个区间里面, a[i] 这个数字出现的次数。
如果当前维持的这个区间里面, a[i] 这个数字出现的次数大于1, j(左边的指针)就要向右挪一个单位,挪动的时候，先让s数组里s[a[j]]--, 再挪动j, 这两步可以写成s[a[j++]]--。
j 永远不会超过i, 当j == i 的时候，代表维持的那个区间就一个数, 所以check(i, j)是false, while就会结束。
所以这里while里只需要写check(i, j) 就可以了。

C++ 代码

#include<iostream>

using namespace std;

const int N = 1e5 + 10;
int a[N], s[N];
int n;

int main(){
    scanf("%d", &n);
    for(int i = 0; i < n; i++) scanf("%d", &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++]]--;
        res = max(res, i - j + 1);
    }

    cout << res << endl;

    return 0;
}