3 条题解

  • 0
    @ 2024-4-7 12:58:38
    #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 
    }
    

    信息

    ID
    91
    时间
    1000ms
    内存
    256MiB
    难度
    6
    标签
    (无)
    递交数
    579
    已通过
    157
    上传者