脚本宝典收集整理的这篇文章主要介绍了C++题解 最长连续不重复子序列,脚本宝典觉得挺不错的,现在分享给大家,也给大家做个参考。
给定一个长度为 n 的整数序列,请找出最长的不包含重复的数的连续区间,输出它的长度。
第一行包含整数 n。
第二行包含 n 个整数(均在 0∼105 范围内),表示整数序列。
共一行,包含一个整数,表示最长的不包含重复的数的连续区间的长度。
(1≤n≤105)
5
1 2 2 3 5
3
暴力算法显然是最容易考虑的,我们使用两个循环 i , j
对整个数列进行遍历,很容易能得到答案。
但是对于大数列,(O(n^2)) 的复杂度很明显就会TLE了
我们使用两个指针 i, j
,令i指向数列下标较大的方向,j 指向数列下标较小的方向,我们每次移动 i, 就检查 ([i, j]) 中是否存在重复数字,若重复,则移动 j 直到不重复。
在这里我们使用计数排序方法,对于每一个在 ([i, j]) 中的数,我们令计数数组 b[n]
中 b[i] ++
,我们每次要把 i 移动的时候,需要判断新加入区间的元素 a[i]
是否与区间存在元素重复,重复,我们就需要对 j 进行移动,移动时 b[j] --
,直到 ([i,j]) 中不重复。
//
// Created by Owwkmidream on 2021/10/31.
//
#include "iostream"
using namespace std;
const int N = 10e5 + 7;
int a[N], b[N];
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n;
cin >> n;
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
int res = 0;
for (int i = 0, j = 0; i < n; ++i) {
b[a[i]] ++;
while(b[a[i]] > 1) {
b[a[j]] --;
j ++;
}
res = max(res, i - j + 1);
}
cout << res;
return 0;
}
以上是脚本宝典为你收集整理的C++题解 最长连续不重复子序列全部内容,希望文章能够帮你解决C++题解 最长连续不重复子序列所遇到的问题。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。