解题思路

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

使用滑动窗口算法。

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

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

P4940.第1题-浏览片段统计

1000ms

Tried: 56

Accepted: 20

Difficulty: 5

所属公司 : 华为

算法与标签>双指针

题目内容

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

输出

说明

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

样例2

输入

5 2
1 40 1 12 5000

输出

说明

不同商品类别数不超过 $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$

输入

预期输出（选填）

解题思路

P4940.第1题-浏览片段统计

题目内容

输入描述

输出描述

样例1

样例2

Status

Development

Support

About