python/TangDou/AcWing/DoublePointer/799.md

##[$AcWing$ $799$. 最长连续不重复子序列](https://www.acwing.com/problem/content/801/)

### 一、题目描述
给定一个长度为 $n$ 的整数序列，请找出 **最长的不包含重复的数的连续区间**，输出它的长度。

**输入格式**
第一行包含整数 $n$。

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

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

**数据范围**
$1≤n≤10^5$

**输入样例**：
```cpp {.line-numbers}
5
1 2 2 3 5
```

**输出样例：**
```cpp {.line-numbers}
3
```

### 二、解题思路

#### 1、朴素思路
```c++
for(int i=1;i<=n;i++)
   for(int j=i;j<=n;j++)
        check(i,j); //看看i-j之间是不是存在某些数值重复
```
因为要执行双重循环，所以时间复杂度是$O(N^2)$,下面我们想办法来优化它。

#### 2、滑动窗口+桶计数

  * 维持一个窗口，这个窗口里面保证是没有重复元素的，窗口大小从$0$开始。左侧有一个慢指针$j$,右侧有一个快指针$i$。

  * 当窗口中没有重复元素时，快指针向右，多吃进来一个。
  
  * 通过桶来判断是不是有重复出现，如果没有，则窗口最大长度++。

  * 如果有重复元素出现，则慢指针不断向右，直到找出并剔除重复元素，此时窗口变小。

  * 在窗口快慢指针的作用下，走完整个数组$i==n$，结束循环。

  * 因为快慢指针只走了一遍数组，可以视时间复杂度为$O(N)$,比两层循环优化太多~

**总结**

双指针，快慢指针，同向。

#### 3、C++ 代码
```cpp {.line-numbers}
#include <bits/stdc++.h>

using namespace std;
const int N = 100010;
int a[N]; // 原数组
int s[N]; // 记个数的桶
int res;

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1, j = 1; i <= n; i++) {
        s[a[i]]++;                       // a[i]这个数在桶中的个数+1
        while (s[a[i]] > 1) s[a[j++]]--; // 如果因为a[i]的加入，导致桶中a[i]的数量大于1
        // 也就是有了重复，则需要从窗口左侧尝试去掉一个，看看情况会不会变好
        // 不断刷新滑动容器长度
        res = max(res, i - j + 1);
    }
    printf("%d\n", res);
    return 0;
}
```