C++ 经典双指针算法
#include<iostream>
using namespace std;
constexpr int N = 1e+5 + 10;
int n;
int arr[N],s[N];
int main()
{
cin >> n;
for(int i = 0; i < n; ++i) cin >> arr[i];
int cnt = 0, j = 0;
for(int i = 0; i < n; ++i)
{
s[arr[i]]++;
if(s[arr[i]] > 1)
while(s[arr[i]] > 1) s[arr[j]] --, j++;
cnt = max(cnt, i - j + 1);
}
cout << cnt << endl;
return 0;
}
本题为经典的双指针算法的模板题,由i开始进行遍历
这里的i表示的含义为不包含重复元素子序列的最右端的端点, j表示的含义不包含重复元素子序列的最左端的端点,这段区间的长度为 i - j + 1; 这道题最关键的应该是如何判断是否有重复元素在子序列中,这里运用了个S[N]数组,这个技巧很巧妙,用arr数组中的值作为s[]数组的下标,然后s[]数组的值表示其对应下标在arr数组中值出现的次数。for循环的遍历从i = 0, j = 0开始, 每次进入循环在s[]数组中对应的位置 ++ 表示在当前的子序列中出现的次数+1, 然后if判断一下当前i遍历到的值是否在s[]数组中的值 > 1, 即表示出现了两次, 因为每次出现重复元素都是新遍历的那个元素可能与当前的子序列有重复,此时需要移动j指针, 先将j下标对应的arr的值,在s[]数组中 –, 然后j指针右移,直到当前子序列没有重复元素,退出while循环,然后更新下当前的cnt的值。