K-K-Bag

链接：https://ac.nowcoder.com/acm/contest/5671/K
来源：牛客网

题意：

给你一个长度为n的数组，数组中的数在1-k之间，问你能否在这个数组的中间形成k-bag，也就是前面几个数和后面几个数可能不满足k-bag条件

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
#define INF 0x3f3f3f3f

int t,n,k;
int a[500005];
unordered_map<ll,int>m;
int f[500005];
int main()
{

    cin>>t;
    while(t--)
    {
        scanf("%d%d",&n,&k);
        bool flag=false;
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
            if(a[i]>k||a[i]<1)flag=true;
            f[i]=0;
        }
        if(flag)
        {
            printf("NO\n");
            continue;
        }
        int cnt=0;
        f[0]=1;
        m.clear();
        for(int i=1;i<=n;i++)
        {
            if(m[a[i]]==0)cnt++;
            m[a[i]]++;
            if(i>k)
            {
                m[a[i-k]]--;
                if(m[a[i-k]]==0)cnt--;
            }

            if(cnt==k||cnt==i)f[i]=i-k>=0?f[i-k]:1;
        }
        m.clear();
        cnt=0;
        for(int i=n;i>=max(n-k,0);i--)
        {
            if(cnt==n-i&&f[i]==1)
            {
                flag=true;
                break;
            }
            if(m[a[i]]==0)cnt++;
            m[a[i]]++;

        }
        if(flag)
            printf("YES\n");
        else
            printf("NO\n");
    }
    return 0;
}