799. 最长连续不重复子序列
算法的模拟过程
s: 0 1 0 0 0 <-- 数组s中1出现1次 ==> s[a[0]] ++; ==>s[1] = 1;
a: 1 2 2 3 5
↑
i, j
s: 0 1 1 0 0 <-- 数组s中2出现1次
a: 1 2 2 3 5
↑
i
↑
j
s: 0 1 2 0 0 <-- 数组s中2出现2次: s[2] = 2
a: 1 2 2 3 5
↑
i
↑
j
执行 while(s[a[i]] > 1)
s: 0 1 1 0 0 <-- 数组s中2出现1次
a: 1 2 2 3 5
↑
i
↑
j <-- 移动左指针j,同时减少重复数2出现的次数
//当扫描到重复数字时 j指针向后移,同时重复数字计数减1, 一直删除到下一个不重复元素位置为止
s: 0 1 1 1 0 1 <-- i指针指向序列最后一个位置,结束扫描
a: 1 2 2 3 5
↑
i
↓
j <-- 更新最长连续区间的长度为i - j = 3
调试:
i j res i-j
2 2 2 0
3
s[i]
0 1 1 1 0 1
#include<iostream>
using namespace std;
const int N = 100010;
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数组存放每个数出现的次数
s[a[i]] ++;
while(s[a[i]] > 1){
//当扫描到重复数字时 j指针向后移,同时重复数字计数减1,一直删除到下一个不重复元素为止
s[a[j]] --;
j ++;
}
//更新最长序列res
res = max(res, i - j + 1);
}
cout << res << endl;
return 0;
}
由于我们是第一次遇到双指针的问题,难免会出现难理解的地方,其实不管是快慢指针/左右指针/滑动窗口,我们要能够理解两个指针ij所指的意义,分别能实现的功能,这样才能让两个指针协同工作来解决问题。
为什么不让j直接指向i呢?
因为s[a[j]] –; 做的是从头开始减去每一个数的计数,而为什么必须从头开始减呢,直接减去重复的数:s[a[i]] –;这样不可以吗?
答案是否定的,因为当出现两个数时,即s数组中出现计数为2的情况时,显然重复的两个数一前一后,我们要做的就是删去前面那个重复的数,而不是想当然的将第一次判重的那个数给删去,为什么?
来看下这个示例:
输入
10
9 3 6 9 5 10 1 2 3 9
输出
cout << i << " " << j << " " << res << " " << i - j << endl;
3 3 3 0
8 8 5 0
9 9 5 0
5
s[i]: 0 1 1 1 0 1 1 0 0 1
标准答案
7
当i指针扫描到第二个9时,循环while(s[a[i]] > 1)开始执行,若我们直接让s[a[i]] –;j = i;显然我们错过了两个数3 6,这两个数将不会重新计入我们最长序列的计数当中。
因此我们要做的就是让j从原位置开始,一步步的找那个重复出现的第一个数(第一个9),将第一个重复的数减去s[9] –;,此时s[9]=1,while循环便不会执行了,之后就是寻找序列中还有没有第二个重复的数(上例中第二个重复的数是3),接着重复上述操作,不断更新最长序列res。
那么就会有第二个问题:如何保证res最大呢?
很明显,i在扫描序列时,如果没有需要重复的数的话,那么会不断更新res = i - j + 1,这样res记录的永远是最大的那个序列的长度。
s[a[i]] ++;
res = max(res, i - j + 1);