双指针
很好理解的一个问题,就只需要解释一下“双指针”是哪一对,以及如何移动的:
1. 用子序列的头尾索引(s,e)作为这一对指针,刚开始都置于0处
2. 首先记录索引e的字符(频数+1)
3. 如果因为这次记录导致了此元素的重复出现,那么就不断的减少索引s的字符频数同时后移s,直到不再出现相同字符为止,反之则什么都不需要做
4. 记录一下从s到e的长度,然后更新最大值,同时e索引需要后移
C++ 代码
#include <iostream>
using namespace std;
constexpr int VALUE_RANGE = 100010;
int cnt[VALUE_RANGE];//元素的范围已给出
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
int* arr = new int[n];
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
int s = 0, e = 0, ans = 0;
while (s < n && e < n) {
cnt[arr[e]]++;//记录
while(cnt[arr[e]] > 1) { //判断是否重复
cnt[arr[s]]--;
s++;
}
ans = max(ans, e - s + 1);//更新
e++;//后移
}
cout << ans << endl;
delete[] arr;
return 0;
}