算法:双指针算法
思路:
i指针从头开始依次遍历每一个数组单元
j指针负责记录数组单元的起始位置
开始时i和j都在开头
在i指针遍历数组单元的同时并且用另一个数组记录下每一个数组单元所出现的次数
如果某个数组单元出现的次数大于1,那么一定是目前i指针所指的位置
因为i指针所指的位置是新记录的数组单元,在i之前没有出现过重复,那么一旦重复出现必在i位置
eg:
1 2 2 3 5
i指针走1,记录,无重复
i指针走2,记录,无重复
i指针走2,记录,有重复。
所以一旦有重复,那么就一定在目前i指针所指的位置。
我们在遍历i指针时,i每移动一次,我们就记录下从i到j的长度。每次移动和前一次进行比较,求出最大值。
并且当i指针在走到有重复的位置的时候就先停下,让j指针跟上,再继续走i指针。
上代码!
#include <iostream>
using namespace std;
const int N=1e5+10;
int a[N],s[N];
int main()
{
int n;
cin>>n;
for(int i=0;i<n;i++) cin>>a[i];
int res=1;//最短长度为1; 因为n的范围。
for(int i=0,j=0;i<n;i++)
{
s[a[i]]++;//记录数组a[i]中每个数出现的次数
while(s[a[i]]>1)
{
s[a[j]]--;
j++;
}
res=max(res,i-j+1);
}
printf("%d\n",res);
return 0;
}
可能有人对下面的代码不理解,我加以叙述。
while(s[a[i]]>1)
{
s[a[j]]--;
j++;
}
一旦发现有某个数在s数组里面出现了两次,马上清除掉前面的记忆(也就是把前面所有的数从s数组里删掉,为了下一次求字符串的长度做准备,同时把指针j移动过来,最后的结果就是i和j移到了一起。并且i指针指的位置在s数组里还留有一个1,因为while的条件是s[a[i]]>1)
Thansk for watching.💕
不一定是i,j遇到一起哦,只要把重复数剔除就跳出循环了。
10
9 3 6 9 5 10 1 2 3 9
这组数据就不是j跟上i,只要去重了就行
第一个元素是9,第四个元素也是9,9出现了两次
当s[a[j]]–的时候,9的次数就被降成1次了,此时j指向的第二个元素。所以说不是任何时候j都和i重叠在一起
1 2 2 3 4 5这组数据是因为2和2黏在一起了,所以j最后会和i重叠
最后面解决了大疑问,你是我的神
每个人卡的点不一样,题解看多慢慢就懂了
nb
太牛逼了哥,看了三份解析,读到你这份我才真正理解。
非常感谢!!!没有你最后那一段我估计我又要蒙圈半天,我感觉y总讲课时而好,时而不好,反正我是这么觉得,还是依靠你们这些人分享啊
去重我懂,但是最后while循环是如何保证连续的呢?
他那个j会一直向前走,知道走到和a[i]重复的那个数字为止,那么这时候他的频率-1,自然while循环就跳出了
现在懂了,谢谢大佬
太赞了,懂了,就是
while(s[a[i]]>1)
{
s[a[j]]–;
j++;
}
这一部分,本来不太明白,然后现在知道了
通俗易懂的题解
写的好