AcWing 799. 最长连续不重复子序列
原题链接
简单
作者:
此题有解否
,
2019-05-30 11:36:19
,
所有人可见
,
阅读 6209
本题的核心思想是双指针算法,i指针是快指针,j是慢指针,每当i指针i指针右移一位的时候,
其对应的元素的个数就需要++,可以看出此处需要一个计数的数组或者unordered_map<int, int>,
如果是字符串或者字符等元素的话,建议用后者。
接下来介绍check函数,check函数的实现功能就是,当s[a[i]]>1的话,我们就持续j++,
并且将s[a[j]]--,这一步绝对不能省。
第三步就是最后的操作了res = max(res, i - j + 1);
#include <iostream>
using namespace std;
const int N = 100010;
int a[N], s[N];
int main()
{
int n = 0, res = 0;
cin >> n;
for(int i = 0; i < n; i ++ ) scanf("%d", &a[i]);
for(int i = 0, j = 0; i < n; i ++ )
{
s[a[i]] ++;
while(j <= i && s[a[i]] > 1)
{
s[a[j]] -- ;
j ++ ;
}
res = max(res, i - j + 1);
}
cout << res << endl;
return 0;
}
s[a[i]] ++;
这个计数的操作为什么必须第二层循环里才行呢
老哥看错了,这就是第一层循环里面的
Orz
这个题没说单调性,能用双指针吗????
不用有单调性
可以推出来J具有单调性
想问下这个题目的单调性你是怎么理解的,i,为何一定j,不是j–呢?
s[a[i]]>1 怎么理解的啊,准确来说 s[a[i]] 这是什么啊,s数组里面一个a数组,a数组是变化的,s[a[i]] ++ 是表示的啥子,具体含义是啥
s数组代表着a[i]出现了多少次,s[a[i]] ++出现的次数加1
感谢啦,我理解了
更改为 while(s[a[i]] > 1) 更好理解
第18行 并不需要判断 j 和i 的大小关系,有后半句限制范围 j 怎么可能追得上i吗= =
?那半句话话啊,怎么就限制j了?
while(s[a[i]] > 1) 改成这样就可以了
快指针,慢指针
这个形象
为什么必须s[a[j]] –不是很理解啊
我想明白了 是为了避免重复序列的问题… 不然的话重复序列会被算进去
对不起呀 现在才看到 最近忙着毕业设计 都没怎么刷题了