本文共 951 字，大约阅读时间需要 3 分钟。

题目大意：

给n个数， n<=100W，求一个连续子序列，这个子序列中没有重复的数，问这个子序列最长是多少？

思路：

开一个数组pos，  pos[ x ] 表示x出现的位置， 这个数组初始化为-1

用一个变量start来记录当前枚举序列的起点，初始为0

然后枚举这个序列，依次记录每个数的位置，

假设当前枚举到i， 在记录这个位置之前，先检查当前这个数的位置pos【 arr【i】 】是否大于等于start，如果大于，说明这个数已经在[start, i-1]中已经出现过了，记下这个满足条件的子序列长度。然后枚举下一个子序列： start = pos[i] + 1.  这个算法总复杂度为O(n)

代码：

/* * UVa 11572 Unique Snowflakes * */#include
   
    #include
    
     #include
     
      using namespace std;typedef long long int64;const int INF = 0x3f3f3f3f;const int MAXN = 1000010;int arr[MAXN];int pos[MAXN];int main(){    int nCase, m, n;    scanf("%d", &nCase);    while(nCase--){                scanf("%d", &n);        int cnt=0;        for(int i=0; i
      
       = start){                int tmp = i - start;                maxx = max(tmp, maxx);                start = pos[arr[i]]+1;                pos[arr[i]] = i;            }else{                pos[arr[i]] = i;            }        }        printf("%d\n", maxx);    }    return 0; }
      
     
    
   

转载地址：http://rszni.baihongyu.com/