双指针

时间复杂度 $O(n)$

因为 i , j 都不会向左移动， 所以只会遍历数组一遍
i 遍历一遍 $O(n)$
j 遍历一遍 $O(n)$

最坏的情况是 $a[n - 1] == a[n - 2]$ 此时 $i 执行 n 次， j 在while 中也执行 n 次$
所以最坏情况下 $O(n) + O(n) = O(2n) = O(n)$

输入样例

1 2 3 4 5 3 6 7 8

输出样例

6

样例解释

用 快指针i, 慢指针 j 来遍历数组
在 i < 5 时, while 语句 都不会执行，所以 vis[] = {1,1,1,1,1,0,0,0,0} $res = 5$
当 i == 5 时,

• ++vis[a[i]];
• while
  vis[] = {1,1,2,1,1,0,0,0,0}
  vis[] = {0,1,2,1,1,0,0,0,0}
  vis[] = {0,1,2,1,1,0,0,0,0}
  vis[] = {0,0,1,1,1,0,0,0,0}

此时 $res = 5$
再往后 while 语句就不再执行了，所以读到最后 $res = 6$

再解释一下 i - j + 1 , 这个举个例子就可以了

• 当 $i = 3 , j = 5$, 长度应该为 {3 , 4, 5} 应该是3， $5 - 3 + 1 = 3$

C++ 代码

#include <iostream>
using namespace std;

const int N = 100010;
int vis[N];
int a[N];

int main() {
    int res = 0;
    int n;
    cin >> n;
    for (int i = 0; i < n; i ++ ) cin >> a[i];

    for (int i = 0, j = 0; i < n; i ++ ) {
        ++vis[a[i]];
        // j < i 理所当然的
            // vis[a[i]] > 1 说明 a[i]的左边存在一个 和a[i]相等的数
            // 所以用 vis[a[j]] 探测这个数在哪里
            // 如果 当 vis[a[j]] 减一  之后 vis[a[i]] <= 1 ,
            // 说明 j 已经找到 那个数了, 并且停留在那个数的右边
            // 如果 当 vis[a[j]] 减一  之后  vis[a[i]] > 1 仍成立,
            // 说明没有找到 正确的位置，而且 指针 j 前面的数已经不会用到了
            // 为了不影响后面的计算， 也要将 vis[a[j]] -- 来 将 a[j] 从 vis[]数组中消除一个
        while(j < i && vis[a[i]] > 1) {
            --vis[a[j++]];
        }
        res = max(res, i - j + 1);
    }
    cout << res << endl;
    return 0;

}