题目描述

用双指针算法来求出最长的一段重复的子区间（数组是提前排好序的）

背模板时需要理清的思路

本题用到的是第一类双指针算法。
本题要用双指针算法是因为i、j指针移动是具有单调性的且j一直在i后面

图中圈圈代表的是s[N]中依次存入的值

双指针算法的具体步骤：
①第一步是构造值域数组s[N],这个数组存的值并不是值域，而是值域中每个值出现的次数。s[a[j]] –;j ++ 是让j指针扫过的区域都减1，注意最终j停在最后一次减1的的下标的右面，可以使重复序列的最后一个数参与输出。
②第二步计算最长序列用max(res, i - j + 1),原因是如果每次循环只移动i不移动j则这次循环一定是找到了不重复的子序列，此时res会记录下本次不重复长度i - j + 1。而如果又碰到了新的重复子序列的时候j就会移动直到i这里，所以res存入之前记录下来的长度通过max函数处理会被保留。

代码写法上的特点

①s[a[i]] ++是直接将下标a[i]对应的值的次数加1，与之前的排序模板中出现的s[a[i] ++ ]不太一样

参考文献

参考y总的代码

C++ 代码

#include <iostream>

using namespace std;

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

int main()
{
    int n;
    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;

}