4394. 最长连续子序列

4394. 最长连续子序列

思路：
数字的范围在0 ~ 1e6之间，所以可以开一个数组，存每个数字的出现次数。

双指针枚举区间，diff统计不同的数字个数，maxlen维护区间的长度，如果双指针区间大于maxlen，则更细l,r。

代码：

#include<iostream>
using namespace std;
int n,k;
const int N = 5e5+10,M = 1e6+10;
int cnt[M];
int maxlen;//双指针区间长度
int diff;//不同的字符个数
int l,r;
int a[N];

int main(){
    cin>>n>>k;
    for(int i = 0; i < n; i++) cin>>a[i];
    
    for(int i = 0, j = 0; i < n; i++){
        if(!cnt[a[i]]) diff++;
        cnt[a[i]]++;
        
        if(diff <= k){
            if(maxlen < i - j + 1){
                maxlen = i - j + 1;
                l = j + 1,r = i + 1;
            }
        }
        else{
            while(diff > k){
                int tmp = a[j++];
                cnt[tmp]--;
                if(!cnt[tmp]) diff--;
            }
        }
    }
    cout<<l<<" "<<r;
    
    return 0;
}