基础算法复习:双指针算法
题目描述
给定一个长度为n的整数序列,请找出最长的不包含重复的数的连续区间,输出它的长度。
输入格式
第一行包含整数n。
第二行包含n个整数(均在0~100000范围内),表示整数序列。
输出格式
共一行,包含一个整数,表示最长的不包含重复的数的连续区间的长度。
数据范围
1≤n≤100000
样例
输入样例:
5
1 2 2 3 5
输出样例:
3
审题
本题的目标是求没有重复数出现的区间的最大长度,即求具有某种性质的区间的最大长度,可以使用第一类双指针算法。
算法
双指针算法。
大致的思路是用两个指针维护一段区间,对于每一个右端点i的值,需要求出j最小可以是多少。(而随着i变大,j一定是变大或者不变的(假设i变大j可能变小,那么对于之前的i,当前的j才是可能的最小的j,因为一段无重复数区间的子区间也不会有重复数,这就产生了矛盾)。这种单调性质也是可以用双指针算法来优化朴素做法的原因,这样就不需要每次都从j=0开始,减少了无意义的计算。)对于当前的i来说,j最小只能到使得a[i]不重复出现的位置。每次j停下后,更新答案。全部循环结束后就可以得到答案。
具体实现时需要解决的问题
两个指针维护一段区间:用i,j初始分别指向起点,然后按规则移动。
判断是否遇到了重复数:另开一个数组,记录该数组元素下标的数字的出现次数,每次i移动后就将a[i]出现的次数加一,每次更换区间起点时就将a[j]出现的次数减一,判断a[i]是否重复出现只需要判断a[i]出现的次数是否大于1.
C++ 代码
#include <iostream>
#include <cstdio>
using namespace std;
const int N=100010;
int a[N],c[N];
int main(){
int n;
cin>>n;
int res=0;
for(int i=0;i<n;i++) scanf("%d",&a[i]);
for(int i=0,j=0;i<n;i++){
c[a[i]]++;
while(j<i&&c[a[i]]>1) c[a[j++]]--;
res=max(i-j+1,res);
}
cout<<res<<endl;
return 0;
}