算法1
(双指针(尺取法)+哈希离散化) $O(n)$
blablabla
时间复杂度
参考文献
C++ 代码
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
#include <map>
#define null 0x3f3f3f3f
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
int n;
const int M=2000010;
const int N=2000003;
int h[M];//哈希表
int a[M];
int find(int x)//哈希离散化
{
int k=(x%N+N)%N;
while(h[k]!=null&&h[k]!=x)
{
k++;
if(k==N) k=0;
}
return k;
}
//思路:
//哈希表存某一种类的雪花是否在当前双指针枚举的区间内
//每一次枚举,在后指针向右移动一格之前,区间内的雪花种类是两两不同的
//当向右移动了一格后,原区间内可能也有种类为a[j]的雪花,此时需要将双指针前移至与a[j]重复的雪花的后一个位置
//每一次尺取后,更新最大长度
int main()
{
cin>>n;
int x;
memset(h,0x3f,sizeof h);
for(int i=1;i<=n;i++) cin>>a[i];
int res=0;
for(int j=1,i=1;j<=n;j++)
{
while(i<j&&h[find(a[j])]!=null) h[find(a[i++])]=null;//每一种雪花在当前枚举区间内只出现一次,所以在i指针向右移动后,可以直接将其删除
h[find(a[j])]=a[j];//当前区间新增加了这片雪花,将这片新雪花加入到哈希表中
res=max(res,j-i+1);//更新答案
}
cout<<res;
return 0;
}
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla