AcWing 799. 最长连续不重复子序列(双指针算法 & c++ &python)
原题链接
简单
作者:
李先潴
,
2021-11-04 19:21:34
,
所有人可见
,
阅读 395
这个c++的注释不知道为啥没高亮
c++(注释带输出路径方法)
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100010;
int q[N],a[N]; //q[N]储存输入的数组,a[N]储存每个数出现的次数
int n;
int main()
{
scanf("%d", &n);
for (int i = 0; i < n; i ++ ) scanf("%d", &q[i]);
int res;
int l,r;
for (int i = 0,j=0; i < n; i ++ )
{
a[q[i]]++;
while(j<i&&a[q[i]]>1)
{
a[q[j++]]--; //将q[j]这个元素拿出去,并让j向i靠近,直到j,i之间没有重复的元素
}
// if(res<i-j+1){l=j,r=i;} //加一个l,r可以查看最长不重复子序列是哪一段
res=max(res,i-j+1);//用max求出最长的
}
cout<<res<<endl;
// for(int i=l;i<=r;i++)cout<<q[i]<<" ";//输出该最长子序列
return 0;
}
python
n=int(input()) # 输入n和整个序列
a=list(map(int,input().split()))
s=[0]*(n+1) # s[] 存储当前序列中每个字符出现的次数
res=0 # 结果
for i in range(n):
s[a[i]]+=1 # 当前字符出现的次数+1
while s[a[i]]>1: # 如果当前字符出现次数>1,表示有重复,需要进行处理
s[a[j]]-=1 # 让j开始往右走,走一次,看一次是否还有重复
j+=1
res=max(res,i-j+1) # 更新答案
print(res)