双指针算法-枚举左端点
大部分题解都是枚举右端点,那么就写一篇枚举左端点的题解。
详情见注释,注释很详细。
#include <cstdio>
#include <iostream>
using namespace std;
const int N = 100010;
int a[N], c[N];
int main()
{
int n;
scanf("%d", &n);
for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
int ans = 1;
// 此处c[0]在开始循环时一定会归0
c[0] = 1; // 见a处
for (int i = 1, j = 1; i <= n; ++i)
{
// a:弹出上一个起点
--c[a[i - 1]];
/*
求出首个有重复数字的区间[i, j]
[i, j - 1]即为无重复数字的区间
注意:如果没有将c[0] = 1,第一次遇到0时会认为其已经出现过了!(-1) = true
*/
while (!c[a[j]] && j <= n) c[a[j]]++, j++;
// (j - 1) - i + 1 = j - i
if (j - i > ans) ans = j - i;
}
printf("%d\n", ans);
return 0;
}