题意：输入长度为n的序列a，找到一个尽量长的连续子序列a[l] - a[r]，使该序列中没有相同的元素
紫薯P239
序列元素从0开始编号，l 和 r 分别表示子序列左右端点，初始化为0，固定 l，判断加入 a[r] 是否重复，如不重复，加入，同时r++，若重复，l++，然后再判断加入a[r]是否重复..
时间复杂度：r从0到n，判重由set来处理lgn，总O(nlgn）
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <set>
using namespace std;
int main()
{
int t, n;
scanf("%d", &t);
while (t--)
{
scanf("%d", &n);
int *a = new int[n]; //动态分配
for (int i = ; i < n; i++)
scanf("%d", &a[i]);
int l, r, maxL;
maxL = l = r = ;
set<int> s;
while (r < n)
{
while (r < n && s.count(a[r]) == ) //判断加入r是否重复
{
s.insert(a[r]);
r++;
}
maxL = max(maxL, r - l);
s.erase(a[l]); // 将l处的移除set
l++;
}
printf("%d\n", maxL);
}
return ;
}
用map来求
last[i] = x表示第i各位置的数上一次出现是在第x位置，故对于 r 位置的数来说，如果他上次出现在 l 位置之前，则 r 是可以扩展的，否则 l++;
记录每个位置上一次出现的位置可以用map来映射。
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <set>
#include <map>
using namespace std;
int main()
{
int t, n;
scanf("%d", &t);
while (t--)
{
scanf("%d", &n);
int *a = new int[n];
int *last = new int[n];
map<int, int> m;
for (int i = 0; i < n; i++)
{
scanf("%d", &a[i]);
if ( m.count(a[i]) == 0 )
{
last[i] = -1; // 如果上次没有出现，设为-1
}
else
{
last[i] = m[ a[i] ]; // 如果上次出现，找到上次出现的位置
}
m[ a[i] ] = i; // 这次出现的位置
}
int l, r, maxL;
l = r = maxL = 0;
while (r < n)
{
while (r < n && last[r] < l) // 一定是last[r] < l时，r才加一
r++;
maxL = max(maxL, r - l);
l++;
}
printf("%d\n", maxL);
delete[] a;
delete[] last;
}
return 0;
}