$\Huge\color{orchid}{点击此处获取更多干货}$
双指针
很好理解的一个问题,就只需要解释一下“双指针”是哪一对,以及如何移动的:
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;
}