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

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] 区间内出现过，那次数会变成2
			cnt[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] 区间内出现过，那次数会变成2
			mp[a[j]] --; // 从区间开始位置 j 的那个数依次往前去掉，知道遇到与a[i]值相同的为止，
			j ++;
		}
		res = max(res, i - j + 1);
	}
	
	cout << res << endl;
	return 0;
}