[题解] 周赛 Round 43:D 小红的子数组排列判断

D 小红的子数组排列判断

题意:

给定一个长度为n的数列, 找出1-k的连续组合排列个数

思路:

本题可使用双指针维护一个长度为k的滑动区间, 在区间内判断当前区间是否符合要求.

具体如何判断?

这里运用了哈希表及统计量"不同元素个数"来判断.
每次滑动后, 将退出元素哈希值自减, 加入元素哈希值自增, 然后根据它们的哈希值更新"不同元素个数". 区间内 "不同元素个数"==k 则该区间符合要求.

或者运用c++中stl:set的特性(目前还没学会)

错误原因:

首先呢也是读错了题, 没注意到是排列, 即乱序的1-k也是符合要求的, 于是写了个错的暴力
快结束时才发现思路错了, 哎呀.
然后也是写的哈希表来判断, 不过用的遍历, 超时了...

输入:

n,k
n个正整数ai

输出:

一个整数，代表长度为k的连续子数组是排列的数量

AC代码:

#include <bits/stdc++.h>
using namespace std;

int num[100005], hash1[100005] = {0, 0};

int main()
{
	int n, k;
	cin >> n >> k;
	for (int i = 0; i < n; i++)
	{
		cin >> num[i];
	}

	//双指针划分滑动区间, 用不同数字个数和哈希表维护区间状态, 区间挪动时进行更新
	int sum = 0;
	int differ = 0;
	for (int i = 0; i < k; i++) //维护第一个区间
	{
		if (hash1[num[i]] == 0)//塞入元素
		{
			differ++;
		}
		hash1[num[i]]++;
	}
	if (differ == k)//判断是否合法
		sum++;
	for (int i = 1, j = k; i <= n - k && j < n; i++, j++)
	{
		//每次滑动到后一个区间

		hash1[num[i - 1]]--; //踢掉前一个
		if (hash1[num[i - 1]] == 0)
		{
			differ--;
		}

		if (hash1[num[j]] == 0)//加入后一个
		{
			differ++;
		}
		hash1[num[j]]++;

		if (differ == k)//判断是否合法
			sum++;
	}
	cout << sum;
	return 0;
}