一、题目描述
给 定 一 个 长 度 为 n 的 整 数 序 列 , 请 找 出 最 长 的 不 包 含 重 复 的 数 的 连 续 区 间 , 输 出 它 的 长 度 。 给定一个长度为 n 的整数序列,请找出最长的不包含重复的数的连续区间,输出它的长度。给定一个长度为n的整数序列,请找出最长的不包含重复的数的连续区间,输出它的长度。
输入格式
第 一 行 包 含 整 数 n 。 第一行包含整数 n。第一行包含整数n。
第 二 行 包 含 n 个 整 数 ( 均 在 0 ∼ 1 0 5 范 围 内 ) , 表 示 整 数 序 列 。 第二行包含 n 个整数(均在 0∼10^5 范围内),表示整数序列。第二行包含n个整数(均在0∼10
5
范围内),表示整数序列。
输出格式
共 一 行 , 包 含 一 个 整 数 , 表 示 最 长 的 不 包 含 重 复 的 数 的 连 续 区 间 的 长 度 。 共一行,包含一个整数,表示最长的不包含重复的数的连续区间的长度。共一行,包含一个整数,表示最长的不包含重复的数的连续区间的长度。
数据范围
1 ≤ n ≤ 1 0 5 1≤n≤10^51≤n≤10
5
输入样例:
5
1 2 2 3 5
1
2
输出样例:
3
————————————————
双指针方法
//会超时,要优化
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 100010;
int n;
int q[N];
//check——是否有重复的2个数, 有返回false,无返回true
bool check(int left, int right)
{
for(int i = left; i <= right; i++){
for(int j = i; j <= right; j++){
if(i != j && q[i] == q[j]){
return false;
}
}
}
return true;
}
int main()
{
scanf("%d", &n);
for(int i = 1; i <= n; i++){
scanf("%d", &q[i]);
}
int res = 1;
for(int i = 1; i <= n; i++){
for(int j = i; j <= n; j++){
if(check(i, j)){
res = max(res, j - i + 1);
}
}
}
printf("%d\n",res);
return 0;
}
__在双指针基础上优化____
//节省一层for循环(for(j)),可以不循环
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 100010;
int n;
int q[N];
int cnt[N]; //记录每个数字出现的次数
int main()
{
scanf("%d", &n);
for(int i = 1; i <= n; i++){
scanf("%d", &q[i]);
}
int res = 1;
for(int i = 1, j = 1; i <= n; i++){
cnt[q[i]]++;
while(cnt[q[i]] > 1){
cnt[q[j]]--; //如果有一个数出现2次及以上,就把前面的“数删掉”(把前面不符合的数的出现次数也减去)(重置数组),再把j的指针移到和i指针同一个数上,重新开始循环
j++;
}
res = max(res, i - j + 1);
}
printf("%d\n", res);
return 0;
}
整 数 序 列——单调不减的(有平有增) (—/----/)