799.最长连续不重复子序列

题目来源：

AcWing - 算法基础课

---

题目内容：

给定一个长度为 n的整数序列，请找出最长的不包含重复的数的连续区间，输出它的长度。

输入格式

第一行包含整数 n。

第二行包含 n个整数（均在 0∼105范围内），表示整数序列。

输出格式

共一行，包含一个整数，表示最长的不包含重复的数的连续区间的长度。

数据范围

1≤n≤105

输入样例： 5 1 2 2 3 5 输出样例： 3

---

思路分析：

双指针算法

---

代码实现： #include <iostream> using namespace std; const int N=100010; int a[N],s[N];//s[N]：记录每个元素的个数 int main(){ int n,r=0; cin>>n; for(int i=0,j=0;i<n;++i){//注意这里i++的写法 cin>>a[i]; ++s[a[i]]; while(s[a[i]]>1){//当a[i]重复时，先把a[j]次数减1，再右移j。 --s[a[j++]]; //有点懂了 } r=max(r,i-j+1);//i-j+1:是指2，3，5一共有三个数字 } cout<<r; return 0; }

---

题目心得： 代码在dev上运行没有问题，但是提交到AcWing上就是不通过，我的写法和类似正确题解的写法几乎没有出入，这种情况，遇到已经不止一次了这里如果不理解这道题的《双指针》思路，推荐大家去看这个博主（图解写得很棒）