返回题解分享
讨论 / 题解分享/ 帖子详情

最长连续不重复子区间 - 题解

#include <bits/stdc++.h>
#define objl '\n'
typedef long long ll;
using namespace std;
//数据结构在这里定义

const int N = 1e6 + 10;
int arr[N];
int n,x; 

////区间是否不重复
//超时了
//bool valid(int s, int e){
//	set<int> tmp;
//	for(int i = s;i<=e;i++){
//		if(tmp.find(arr[i])!=tmp.end())
//			return false;
//		tmp.insert(arr[i]);
//	}
//	return true;
//}

void solve(){
	cin >> n;
	for(int i = 1;i<=n;i++){
		cin >> arr[i];
	}
	//滑动窗口
	int maxlen = -1;
	int start_id = 1; 
	map<int, int> tmp;//帮助去重 
	
	for(int end_id = 1; end_id <=n; end_id++){
		//for循环开始时 arr[end_id]加入了子序列,让序列变长 
		tmp[arr[end_id]]++;
		//验证是否符合不重复要求
		//最长子序列,只有不满足条件才考虑移动start_id
		//如果是最短,那只要满足条件就移动start_id 
		while(tmp[arr[end_id]]>1){
			//重复了,说明子序列太长了,右移start_id缩短 
			//直到重新满足不重复
			tmp[arr[start_id]]--;
			start_id++; 
		} 
		//此时满足不重复,更新长度
		maxlen = max(maxlen, end_id - start_id + 1); 
	}
	cout << maxlen << endl;

}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;//多组数据要cin
	//cin >> t;
	t = 1;
	while(t--){
		solve();
	} 
	return 0;//必须加return 0 
}
0 回复 0 转发 0 喜欢 6 阅读
回复 (0)
默认 最新
暂无回复,快来抢沙发!