Awcing 799. 最长连续不重复子序列

解题思路:

让我们找到一个数组中，最长的 不包含重复的数 的连续区间的长度。

最优解是双指针算法：

• 我们用$cnt[i]$记录 $i$ 这个整数在区间内出现的次数。(因为每个数的大小为$10^5$, 存的下)。

代码如下：

#include<iostream>using namespace std;
const int maxn = 1e5 + 10;int a[maxn];
int cnt[maxn];int main(){int n;cin >> n;int res = 0;for(int i = 1, j = 1; i <= n; i ++ ) {cin >> a[i];cnt[a[i]] ++; // 将 a[i] 出现次数 ++while(cnt[a[i]] > 1) { // 如果在 [j, i - 1] 区间内出现过，那次数会变成2cnt[a[j]] --; // 从区间开始位置 j 的那个数依次往前去掉，知道遇到与a[i]值相同的为止，j ++;}res = max(res, i - j + 1);}cout << res << endl;return 0;
}

数据加强版： 如果说我们把每个数的大小规定为$[1,10^9]$, 那显然就不能用数组来保存每个数出现的次数，开不了这么大的数组。于是我们就可以把这些数离散化。(因为最多有$10^5$个点)。

代码如下：

#include<iostream>
#include<unordered_map>using namespace std;
const int maxn = 1e5 + 10;int a[maxn];unordered_map<int, int> mp; // 离散化存储int main(){ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int n;cin >> n;int res = 0;for(int i = 1, j = 1; i <= n; i ++ ) {cin >> a[i];mp[a[i]] ++; // 将 a[i] 出现次数 ++while(mp[a[i]] > 1) { // 如果在 [j, i - 1] 区间内出现过，那次数会变成2mp[a[j]] --; // 从区间开始位置 j 的那个数依次往前去掉，知道遇到与a[i]值相同的为止，j ++;}res = max(res, i - j + 1);}cout << res << endl;return 0;
}