题目描述
blablabla
样例
//////////////////最长连续不重复子序列
//////////////////经典双指针-----i和j的思想,
#include <bits/stdc++.h>
using namespace std;
#define QAQ "QAQ"
#define x first
#define y second
const int N = 1E5 + 11;
int t, n, a[N];
bool cnt[N];///也可以用桶来记录(-^-)
////最长连续不重复子序列
void work(){
int ans = -1;
memset(a, 0, sizeof(a));
for(int i = 1; i <= n; ++ i) cin >> a[i];
//双指针枚举
for(int i = 1, j = 1; i <= n && j <= n; ++ i){
while(!cnt[a[j]] && j <= n) cnt[a[j ++]] = true;
//-------------------------------------
ans = max(ans, j - i);
while(a[i] != a[j]){
cnt[a[i]] = false;
++ i;
}
cnt[a[i]] = false;
}
cout << ans << '\n';
}
int main()
{
//ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> t;
for(int i = 1; i <= t; ++ i){
cin >> n;
work();
}
system("pause");
return 0;
}
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla