题目：输入一个长度为n（n<10e6）的序列A，找到一个尽量长的连续子序列AL~AR，使该序列内没有重复元素
分析：简单来讲就是遍历数组，定L定R，这就O（N2）了，再判断是否有相同元素，差不多是O（N3）；仔细想想，其实定L，定R，如果满足，让R+1，如果不满足，让L+1，复杂度为O（N），判断是否相同元素用set，set的插入删除和查找都是O（logN）
说明：起初我直接输出R-L+1，发现结果不对，例如 1234444444，很明显最后结果R-L+1为1，但最大长度是4
#include <iostream> #include <algorithm> #include <set> using namespace std; const int MAXN=10e6+10; int arr[MAXN]; int main() { int T; cin>>T; while(T--) { int n; cin>>n; for(int i=0; i<n; i++) cin>>arr[i]; int l=0,r=0,res=0; set<int> s; for(l=0; l<n; l++) for(; r<n; r++) { if(!s.count(arr[r])) { s.insert(arr[r]); res=max(res,r-l+1); } else { s.erase(arr[l]); break; } } cout<<res<<endl; } }
