ZYF003 最长连续不重复子序列
大约 1 分钟
ZYF003 最长连续不重复子序列
【算法】 双指针、滑动窗口
【C++】 双指针、cnt数组
【难度】 普及−
一、题目简述
给定长度为 的整数序列,找最长的不包含重复数的连续区间,输出长度。
二、解题思路
双指针维护不重复区间 。用 cnt 数组记录窗口内每个数的出现次数。
- 右移,
cnt[a[r]]++ - 如果
cnt[a[r]] > 1(出现重复), 右移,cnt[a[l]]--,直到cnt[a[r]] == 1 - 每步窗口 内无重复,更新答案
手动模拟 [1,2,2,3,4]:
- r=1: {1}, len=1
- r=2: {1,2}, len=2
- r=3: 2重复,l++ → {2,2},2仍重复,l++ → {2}, len=1
- r=4: {2,3}, len=2
- r=5: {2,3,4}, len=3 → 最长=3
三、参考代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int a[N], cnt[N];
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
int l = 1, ans = 0;
for (int r = 1; r <= n; r++) {
cnt[a[r]]++;
while (cnt[a[r]] > 1) {
cnt[a[l]]--;
l++;
}
ans = max(ans, r - l + 1);
}
cout << ans << endl;
return 0;
}四、复杂度分析
- 时间复杂度:。每个元素最多被加入和移出窗口各一次。
- 空间复杂度:, 为值域大小。注意
cnt数组大小应覆盖所有可能的元素值。
