题解 | #小红的子数组排列判断#

#include<bits/stdc++.h>

using namespace std;

const int N=1e5+10;

int cnt[N],a[N];

int main()

{

int n,k;
cin>>n>>k;
for(int i=0;i<n;i++)cin>>a[i];
int i,j;
int dnt=0;
for(int i=0,j=0;i<n;i++)
{
    cnt[a[i]]++;
    while(cnt[a[i]]>1)
    {
        cnt[a[j]]--;
        j++;
    }
    if(i-j+1==k)
    {
        dnt++;
    }
}
cout<<dnt;
return 0;

} 此代码用了双指针算法，防止了暴力做法导致超时。用cnt数组记录数字出现次数。开始的时候，i和j两个指针指向此数组同一位置，i指针往右走，每走一次记录此数出现的次数，直到此数字出现次数大于一，j指针开始向右移动，让j指针所指的数出现的次数减一，直到i指的数出现次数为一。然后i和j指针继续重复此过程。在此过程中，如果i-j+1与k相等，说明i和j之间出现了全排列，dnt（记录全排列个数）加一。最后输出dnt的值。