题目解析和算法源码

华为OD机试 - 优雅数组（Java & JS & Python & C & C++）_伏城之外的博客-CSDN博客

题目描述

如果一个数组中出现次数最多的元素出现大于等于K次，被称为 k-优雅数组 ，k也可以被称为优雅阈值。

例如

• 数组[1，2，3，1、2，3，1]，它是一个3-优雅数组，因为元素1出现次数大于等于3次
• 数组[1, 2, 3, 1, 2]就不是一个3-优雅数组，因为其中出现次数最多的元素是1和2，只出现了2次。

给定一个数组A和k，请求出A有多少子数组是k-优雅子数组。

子数组是数组中一个或多个连续元素组成的数组。

例如，数组[1,2,3,4]包含10个子数组，分别是： [1], [1,2], [1,2,3], [1,2,3,4], [2], [2,3], [2,3,4], [3], [3, 4], [4]。

输入描述

第一行输入两个数字 n 和 k，以空格隔开，n 是数组 A 的长度，k 是优雅阈值

• 1 ≤ n ≤ 10000
• 1 ≤ k ≤ n

第二行输入 n 个整数，表示给定的数组 A。

• 1 ≤ A[i] ≤ n

输出描述

输出一个整数，表示数组 A 中 k-优雅子数组 的数量，行尾不要有多余空格

用例1

输入

7 3
1 2 3 1 2 3 1

输出

1

说明

只有子数组 [1,2,3,1,2,3,1] 是 3-优雅数组

用例2

输入

7 2
1 2 3 1 2 3 1

输出

10

说明

10个优雅子数组分别是（下标从0计数）：

长度4：[1,2,3,1]（下标0~3），[2,3,1,2]（下标1~4），[3,1,2,3]（下标2~5），[1,2,3,1]（下标3~6）

长度5：[1,2,3,1,2]（下标0~4），[2,3,1,2,3]（下标1~5），[3,1,2,3,1]（下标2~6）

长度6：[1,2,3,1,2,3]（下标0~5），[2,3,1,2,3,1]（下标1~6）

长度7：[1,2,3,1,2,3,1]（下标0~6）