2022牛客多校第九场

A Car Show

题意： 给定一个长度为n的数组，求包含1~n所有数的区间数量。

思路：

用一个set容器存里面区间的数，用双指针遍历每一个符合条件的区间，每有一个符合的区间，左指针右移；若区间不符合条件，则右指针右移。用哈希表存包含的数。注意开longlong

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+3;
ll n,m;
ll a[N],vis[N];
int main(){
    scanf("%lld%lld",&n,&m);
    set<int> s;
    for(int i=0;i<n;i++)
        scanf("%lld",&a[i]);
    ll ans=0;
    for(int i=0,j=0;i<=n-m;i++){
        while(s.size()!=m) {
            vis[a[j]]++;
            s.insert(a[j]);
            j++;
            if(j>=n) break; 
        }
        if(s.size()==m) ans+=n-j+1;
        vis[a[i]]--;
        if(vis[a[i]]==0) s.erase(a[i]);
    }
    printf("%lld\n",ans);
}