書上把這種問題叫做滑動窗口問題.

我的想法是先進行離散化,然后用一個數組記錄元素出現的位置,如果判斷某個元素已經出現,就將左端點移到上次出現的位置的后面.每次出現重復元素的時候判斷一下答案.我覺得這樣的復雜度是最低的.

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<climits>
#include<cctype>
#include<queue>
#include<set>using namespace std;typedef long long ll;
const int INF=0x3f3f3f3f;
const int MAXN=1e6+5;int a[MAXN],b[MAXN];
int vis[MAXN];
int n,m;
int ans;int main()
{int T;scanf("%d",&T);while(T--){scanf("%d",&n);for(int i=0;i<n;i++) {scanf("%d",&a[i]);b[i]=a[i];}sort(b,b+n);m=unique(b,b+n)-b;for(int i=0;i<n;i++){a[i]=lower_bound(b,b+m,a[i])-b;}memset(vis,-1,sizeof(vis));int l=0,r=0; ans=0;while(r<n){if(vis[a[r]]!=-1){ans=max(ans,r-l);for(int i=l;i<vis[a[r]];i++){vis[a[i]]=-1;}l=vis[a[r]]+1;vis[a[r]]=r;r++;}else{vis[a[r]]=r;r++;}}ans=max(ans,r-l);printf("%d\n",ans);}return 0;
}

出現了一個問題就是我剛開始標記的位置可能為0,可是我判斷元素出現也是用的0,然后就出現錯誤了,這是一種危險的做法,以后還是盡量用-1,也挺方便的.

還有就是每次出現重復元素的時候才判斷答案,可是如果一直沒有出現重復答案的話就有可能沒有更新答案,所以在最后要記得更新答案.

看了一下書上的做法,一種用的是set,我覺得那個復雜度挺高的,可是人家也能過.還有一種用的map,我覺得用map也挺好,他還用了一個數組,我覺得用map的話就沒有必要用數組記錄了,也不用進行離散化了.
發現map可以進行判斷值是否出現過,之前都不知道.

我用map又寫了一個.

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<climits>
#include<cctype>
#include<queue>
#include<set>
#include<map>using namespace std;typedef long long ll;
const int INF=0x3f3f3f3f;
const int MAXN=1e6+5;int a[MAXN];
int n,m;
int ans;
map<int,int> vis;int main()
{int T;scanf("%d",&T);while(T--){vis.clear();scanf("%d",&n);for(int i=1;i<=n;i++) {scanf("%d",&a[i]);}int l=1,r=1; ans=0;while(r<=n){if(vis[a[r]]!=0){ans=max(ans,r-l);for(int i=l;i<vis[a[r]];i++){vis.erase(a[i]);}l=vis[a[r]]+1;vis[a[r]]=r;r++;}else{vis[a[r]]=r;r++;}}ans=max(ans,r-l);printf("%d\n",ans);}return 0;
}