解题思路

本题要求统计连续浏览片段中，不同商品类别数不超过 $k$ 的片段数量。

使用滑动窗口算法。

维护一个窗口 $[left, right]$，表示当前连续片段。用哈希表记录窗口内每种类别出现的次数，同时维护不同类别数量。

每次将 $nums[right]$ 加入窗口：

题目内容

某电商平台需要分析用户的商品浏览历史，以优化推荐系统。给定用户在某段时间内的商品浏览记录序列，每个商品属于一个类别(如“手机”、“电脑”、“家电”等)。平台希望统计出:用户在连续浏览过程中,不同商品类别数不超过 $k$ 种的浏览片段数量。

浏览片段:浏览记录中一段连续的记录序列。例如,浏览记录 [手机,电脑,手机,家电] 中,[手机,电脑] 是一个浏览片段。

不同商品类别数:浏览片段中不重复的商品类别个数。例如,浏览片段 [手机,电脑,手机,家电] 的不同商品类别数为 $3$(类别为 手机、电脑、家电)。

输入描述

第一行:两个整数 $n$ 和 $k$,用空格分隔

$n$ 表示浏览记录数量 $(1 ≤ n ≤ 10⁵)$

$k$ 表示允许的最大不同商品类别数 $(1 ≤ k ≤ n)$

第二行: $n$ 个整数,表示浏览记录中的商品类别编号 $nums[i](0 ≤ nums[i] ≤ 10⁹)$, 用空格分隔

商品类别编号为唯一标识符,不同的整数代表不同的商品类别

例如:$1001$ 表示"手机",$2002$ 表示"电脑",$3003$ 表示"家电"

输出描述

输出一个整数,不同商品类别数不超过 $k$ 种的浏览片段数量。

样例1

输入

3 3
1001 2002 3003

输出

6

说明

所有浏览片段的不同类别数都不超过 $3$, 因此结果为所有子数组的数量, 即为 $6$

样例2

输入

5 2
1 40 1 12 5000

输出

10

说明

不同商品类别数不超过 $2$ 种的浏览片段 (用 $num[i]$ 表示浏览记录中的第 $i$ 个商品, 第一个商品为 $num[0]$) :

• $num[0]$ ($1$ 种类别: $1$)
• $num[1]$ ($1$ 种类别: $40$)
• $num[2]$ ($1$ 种类别: $1$)
• $num[3]$ ($1$ 种类别: $12$)
• $num[4]$ ($1$ 种类别: $5000$)
• $num[0]$ $num[1]$ ($2$ 种类别: $1、40$)
• $num[1]$ $num[2]$ ($2$ 种类别: $40、1$)
• $num[2]$ $num[3]$ ($2$ 种类别: $1、12$)
• $num[3]$ $num[4]$ ($2$ 种类别: $12、5000$)
• $num[0]$ $num[1]$ $num[2]$ (两个 $1$ 重复, 因此为 $2$ 种类别: $1、40$)

结果为 $10$