用c++写个符合下面要求的代码:给定一个长度为 n 的整数序列,请找出最长的不包含重复的数的连续区间,输出它的长度。 输入格式 第一行包含整数 n 。 第二行包含 n 个整数(均在 0∼105 范围内),表示整数序列。 输出格式 共一行,包含一个整数,表示最长的不包含重复的数的连续区间的长度。 数据范围 1≤n≤105 输入样例: 5 1 2 2 3 5 输出样例: 3
时间: 2023-03-30 19:03:42 浏览: 66
以下是 CSDN 开发的 C 知道的回答:
可以使用双指针来解决这个问题。定义两个指针 left 和 right,分别指向区间的左右端点,同时用一个哈希表记录每个数最后一次出现的位置。每次将 right 向右移动一位,如果当前数已经出现过,就将 left 移动到上一次出现位置的下一位,同时更新哈希表中该数的位置。每次更新区间长度的最大值即可。
以下是代码实现:
#include <stdio.h>
#include <string.h>
#define max(a, b) ((a) > (b) ? (a) : (b))
int n;
int a[100010];
int last[100010];
int left, right;
int ans;
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
}
memset(last, , sizeof(last));
left = 1;
right = 1;
ans = ;
while (right <= n) {
if (last[a[right]] >= left) {
left = last[a[right]] + 1;
}
last[a[right]] = right;
ans = max(ans, right - left + 1);
right++;
}
printf("%d\n", ans);
return ;
}