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

 #include<bits/stdc++.h>

using namespace std;

const int N=1e5+10;

 int cnt[N],a[N];

 bool once(int num[],int k)

{
    for(int p=1;p<=k;p++)
    {
    if(num[p]!=1)
        return false;
    }
  return true;
}
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&&once(cnt,k))
    {
        dnt++;
    }
}
      cout<<dnt;
return 0;
}

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