[双指针] 最长连续不重复子序列(模板题)
程序员文章站
2022-05-06 21:36:06
...
文章目录
1. 双指针
思路:
- 双指针
i, j
维护[j, i]
以a[i]
结尾的最长连续不重复子序列,长度就是i - j + 1
-
i
遍历过的,就哈希表记录,++i
- 当出现重复元素时,一定是
a[i]
与a[j~i-1]
中的某一个元素重复。故就++j
直至[j, i]
这个区间不出现这个重复元素 - 由于
[j, i - 1]
已经是前一步的最优解,此时j
只可能右移以剔除重复元素a[i]
,不可能左移增加元素,因此,j
具有单调性,所以就很适合双指针来降低复杂度。
代码:
#include <iostream>
using namespace std;
const int N = 1e5+5;
int n;
int a[N], st[N];
int main() {
cin >> n;
for (int i = 0; i < n; ++i) cin >> a[i];
int res = 0;
for (int i = 0, j = 0; i < n; ++i) {
st[a[i]] ++;
while (j <= i && st[a[i]] > 1) {
st[a[j]] --;
j ++;
}
res = max(res, i - j + 1);
}
cout << res << endl;
return 0;
}
上一篇: php+mysqli数据库连接的两种方式
下一篇: 二叉树的字符图形显示程序(半期考试)