最长连续不重复子序列是什么，你能给我举个例子吗？
- 内容介绍
- 文章标签
- 相关推荐
本文共计491个文字，预计阅读时间需要2分钟。
题目：给定一个长度为 $n$ 的整数序列，请找出最长的、不包含重复数字的连续区间，并输出它的长度。
输入格式：第一行包含一个整数 $n$。第二行包含 $n$ 个整数，表示序列中的元素。
输出格式：输出一个整数，表示最长的不包含重复数字的连续区间的长度。
题目
给定一个长度为 $n$ 的整数序列，请找出最长的不包含重复的数的连续区间，输出它的长度。
输入格式 第一行包含整数 $n$。
第二行包含 $n$ 个整数（均在 0∼105 范围内），表示整数序列。
输出格式 共一行，包含一个整数，表示最长的不包含重复的数的连续区间的长度。
数据范围 $1≤n≤10^5$
输入样例：
5
1 2 2 3 5
输出样例：
3
思路
步骤如下：
- 遍历存放的整个数组，$l、r$为左右指针
a[i]出现次数b[a[i]] + 1- 存在重复值时左指针 $l$ 右移且对应的值次数减 $1$
- 更新最大值
res = max(res, r - l + 1)
代码
#include <iostream>
using namespace std;
const int N = 100010;
int a[N], b[N]; // a存储数值，b存储第i个数出现的次数
int main()
{
int n;
scanf("%d", &n);
for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);
int res = 0;
for (int l = 0, r = 0; r < n; r ++ )
{
b[a[r]] ++ ; // 对应值出现次数加1
while (b[a[r]] > 1) // 存在重复值则循环
{
b[a[l ++ ]] -- ; // l右移且对应的值出现次数减1
}
res = max(res, r - l + 1); // 更新最大长度
}
printf("%d", res);
return 0;
}
本文共计491个文字，预计阅读时间需要2分钟。
题目：给定一个长度为 $n$ 的整数序列，请找出最长的、不包含重复数字的连续区间，并输出它的长度。
输入格式：第一行包含一个整数 $n$。第二行包含 $n$ 个整数，表示序列中的元素。
输出格式：输出一个整数，表示最长的不包含重复数字的连续区间的长度。
题目
给定一个长度为 $n$ 的整数序列，请找出最长的不包含重复的数的连续区间，输出它的长度。
输入格式 第一行包含整数 $n$。
第二行包含 $n$ 个整数（均在 0∼105 范围内），表示整数序列。
输出格式 共一行，包含一个整数，表示最长的不包含重复的数的连续区间的长度。
数据范围 $1≤n≤10^5$
输入样例：
5
1 2 2 3 5
输出样例：
3
思路
步骤如下：
- 遍历存放的整个数组，$l、r$为左右指针
a[i]出现次数b[a[i]] + 1- 存在重复值时左指针 $l$ 右移且对应的值次数减 $1$
- 更新最大值
res = max(res, r - l + 1)
代码
#include <iostream>
using namespace std;
const int N = 100010;
int a[N], b[N]; // a存储数值，b存储第i个数出现的次数
int main()
{
int n;
scanf("%d", &n);
for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);
int res = 0;
for (int l = 0, r = 0; r < n; r ++ )
{
b[a[r]] ++ ; // 对应值出现次数加1
while (b[a[r]] > 1) // 存在重复值则循环
{
b[a[l ++ ]] -- ; // l右移且对应的值出现次数减1
}
res = max(res, r - l + 1); // 更新最大长度
}
printf("%d", res);
return 0;
}