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

题目传送门

1、朴素思路

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++ 代码

#include <bits/stdc++.h>

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

int main() {
    //优化输入
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    //读入数据
    for (int i = 0; i < n; i++)cin >> a[i];

    int j = 0, res = 0;
    for (int i = 0; i < n; i++) {
        //a[i]的个数++
        s[a[i]]++;
        while (s[a[i]] > 1) { //之所以使用while，是因为当前遇到的a[i],不一定就是a[j],需要不断向前找到a[i]
            s[a[j]]--; //慢指针指向的数字--
            j++;       //慢指针前进一步
        }
        //取结果最大值
        res = max(res, i - j + 1);
    }
    //输出
    cout << res << endl;
    return 0;
}