双指针算法
原题链接
AC源代码
#include <iostream>
using namespace std;
int a[100010], s[100010];
int main()
{
int n ,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;
}
双指针算法原理
以下内容摘自:Alicia编程果果
- 遍历数组
a
中的每一个元素a[i]
, 对于每一个i
,找到j
使得双指针[j, i]
维护的是以a[i]
结尾的最长连续不重复子序列,长度为i - j + 1
, 将这一长度与res
的较大者更新给res
。 - 对于每一个
i
,如何确定j的位置:由于[j, i - 1]
是前一步得到的最长连续不重复子序列,所以如果[j, i]
中有重复元素,一定是a[i]
,因此右移j
直到a[i]
不重复为止(由于[j, i - 1]
已经是前一步的最优解,此时j
只可能右移以剔除重复元素a[i]
,不可能左移增加元素,因此,j
具有“单调性”、本题可用双指针降低复杂度)。 - 用数组
s
记录子序列a[j ~ i]
中各元素出现次数,遍历过程中对于每一个i有四步操作:cin元素a[i]
-> 将a[i]
出现次数s[a[i]]
加1
-> 若a[i]
重复则右移j
(s[a[j]]
要减1
) -> 确定j
及更新当前长度i- j + 1
给res
。
以下内容摘自:Bug_FreeOωO