AcWing 799. 最长连续不重复子序列
原题链接
简单
作者:
yysh
,
2022-12-10 00:12:17
,
所有人可见
,
阅读 117
最长连续不重复子序列
双指针写法
#include<iostream>
using namespace std;
const int N = 100010;
int arr[N];
int tmp[N];
int main() {
int n;
cin >> n;
for(int i = 0; i < n; i++) {
scanf("%d", &arr[i]);
}
int ans = -1;
for(int i = 0, j = 0; i < n; i++) {
//整体的大循环中,或者说这个序列当中,i是不断向后移动的
//当指针i向后移动的时候,i就会指向新的数a[i]
//那么,我们就需要tmp[a[i]]++,表示在目前的[j, i]这个区间中a[i]这个数出现了一次
tmp[arr[i]]++;
//如果指针i向后移动一位,指向新的数a[i],使得tmp[a[i]] > 1
//那说明,在目前的[j, i]这个区间当中,a[i]这个数出现了两次
//由于a[i]是[j, i]区间中的新数,新数是重复的,那就说明之前的位置一定有a[i]
//所以,我们要移动指针j,让其向后移动,尝试去除之前的出现的a[i]
while(j <= i && tmp[arr[i]] > 1) {
tmp[arr[j]]--; //减去当前位置的数的次数,然后再移动j
j++;
//指针j所指的数a[j]在区间[j, i]中可能只出现了一次,但是我们得去除[j, i]中重复的数
//所以指针j需要不断的向后走,哪怕去除只出现一次的数
//只有这样做,我们才能保证[j, i]中元素的唯一性
//当指针j当前所指的数a[j] == a[i],说明[j, i]区间中重复的数找到了
//即,当前位置的j所指的数和当前位置的i所指的数是重复的
//然后我们让tmp[a[j]]--,减去重复的数出现的次数,
//然后让j++,让指针j向后走,让重复的数彻底消失在区间[j, i]中
//这样一来,我们就可以保证,在新的[j, i]区间中,没有重复出现的数了
//这个时候tmp[a[i]] == 1,下次循环就会退出
}
//更新答案,比较当前的答案长度和[j, i]的区间长度
ans = max(ans, i - j + 1);
}
cout << ans;
}