By yusijia

Updated:

Contents
  1. 1. 题目大意：
  2. 2. 分析：

白皮书训练

题目大意：

　　输入一个长度为n(n<=10^6)的序列A,找到一个尽量长的连续子序列AL~AR，使得该序列中没有相同的元素。

分析：

　　用set的特殊性质来存储序列，遍历一遍A数组，如果元素没出现在set中，则R++，并加入set，否则记录此时的序列长度，然后不停的
从set中删除序列元素并L++,直到此时A[R]在序列中没出现过，继续重复上述步骤
set中插入删除都是O(logn)的，所以时间复杂度为O(nlogn)

另一种解法是用map记录上一个相同元素的下标map

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
#include <set>

using namespace std;

int arr[1000005];

int main()
{
    freopen("input.txt", "r", stdin);
    int T, n;
    while(scanf("%d", &T) != EOF){
        while(T--){
            scanf("%d", &n);
            for(int i = 0; i < n; i++){
                scanf("%d", &arr[i]);
            }
            set<int> s;
            s.clear();
            int L = 0, R = 0, ans = 0;
            while(R < n){
                while(R < n && !s.count(arr[R]))
                    s.insert(arr[R++]);
                ans = max(ans, R - L);
                s.erase(arr[L++]);
            }
            printf("%d\n", ans);
        }
    }
    return 0;
}
Contents
  1. 1. 题目大意：
  2. 2. 分析：