一、题意

输入一个长度为n的序列A（n<=1000000），找到一个尽量长的连续子序列，使得序列中没有相同的元素。

二、解析

使用双指针法。或者叫滑动窗口法。
维护一个没有重复元素的窗口，即用i，j分别指向序列中当前窗口的头和尾，为了防止混乱，规定为A[i，j)。然后还需要一个vis数组表示元素是否已经在窗口中了。
我们每次尝试增加j，若A[j]不在窗口中，则可以放心的扩大窗口，并更新答案；若A[j]已经在窗口中出现过了，则我们只好增加i，并逐个从头排出元素，直到把和A[j]相同的那个元素排出来位置（这个元素是一定存在的，只要vis维护正确）。然后更新ans。
就这样直到j达到了n，说明窗口已经滑动到最右端了，已经把所有情况可能的最长子序列尝试过了。

由于i从头到尾只遍历一次，因此时间复杂度为O(n)，不会超时。

三、代码

#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;
const int maxn = 1000000 + 5;
int kase, n, a[maxn], vis[maxn];

int main() {
    cin >> kase;
    while(kase --) {
        cin >> n;
        memset(vis, 0, sizeof(int) * n);
        for(int i = 0; i < n; i ++) cin >> a[i];
        int i = 0, j = 0, ans = 0;
        while(j < n) {
            if(!vis[a[j]]) vis[a[j]] = 1, j ++, ans = max(ans, j - i);
            else {
                while(i < j && a[i] != a[j]) vis[a[i]] = 0, i ++;
                i ++, j ++, ans = max(ans, j - i);
            }
        }
        cout << ans << endl;
    }
}

四、归纳

  • 滑动窗口法，即用i,j双指针（一般用下标）对数组进行遍历，同时要需要一个额外的比如vis数组维护窗口中的元素信息，是一种O(n)的扫描方法。

原题叫 “唯一的雪花”，听起来感觉听凄美的呢... 虽然从来没有仔细看过原题的情景就是了hhhh