华为 · 哈希 · 算法编程题
华为 哈希 N ≤ 1e3 时限 2 秒 / 256 MB

题目描述

小红正在分析商城用户的购物记录。她关心哪些商品经常被同一个用户一起购买。
对于一名用户，如果他购买过两个不同商品 A 和 B，则商品对 (A,B) 的共现次数增加 1。同一名用户的购物记录中可能出现重复商品，同一商品在同一用户处只计算一次。
现在给出 N 名用户的购买记录，以及 Q 次查询。每次查询给定阈值 T，小红想知道共现次数大于等于 T 的不同商品对有多少个。
商品对不区分顺序，即 (A,B) 与 (B,A) 是同一个商品对。

输入输出

输入描述
第一行：两个整数 N, Q
- N ：用户数量 (1 ≤ N ≤ 1000)
- Q ：查询数量 (1 ≤ Q ≤ 200)
接下来 N 行，每行描述一个用户的购物记录：
- 第一个整数 k ：该用户购买的商品数量 (1 ≤ k ≤ 100)
- 接下来 k 个整数：商品 ID ( 1 ≤ 商品 ID ≤ 10000 )
接下来 Q 行，每行一个整数 T
- 查询共现频率 >= T 的商品对数量
输出描述
共 Q 行，每行输出一个整数：满足条件的商品对数量

样例共 1 组

样例 1
输入
5 2
3 1 2 3
1 4
2 2 4
1 5
2 1 3
1
2
输出
4
1

算法解析依据充分

考点：哈希

数据规模 N ≤ 1e3 ｜ 限制 2 秒 / 256MB ｜ 标准输入输出

题目画像

  • 数据规模：N ≤ 1e3，Q ≤ 200，k ≤ 100
  • 元素值域：ID ≤ 1e4（注意整数类型选择，避免溢出）
  • 复杂度门槛：允许 O(n²)；若 n ≤ 300，O(n³) 通常也跑得动，需看具体常数。
  • 源站时限：2 秒（牛客口径，非本题专属门槛）

解题思路

推荐方向：哈希

本题切入点

用哈希表统计商品对共现：同一用户内先对商品去重，再两两组合（键用有序对）计数，最后按阈值 T 统计或逐查询统计满足条件的商品对数。

用哈希表把「查找/计数」的开销降到 O(1) 均摊。

思路框架（哈希 通法 · 非本题专属）

  1. 一次遍历，把元素作为 key、出现次数/首次位置作为 value 存进哈希表。
  2. 第二次遍历（或边扫边查）拿到需要的信息。
  3. 注意哈希无序：需要按原顺序输出时要额外记录顺序。

实现要点：Python 用 dict / collections.Counter / defaultdict；C++ 用 unordered_map。

复杂度：时间 O(n) 均摊 ｜ 空间 O(n)

该范式的通法易错点

  • 遍历哈希表时依赖了不存在的顺序。
  • 多次查询时每次都重新统计。

对照本题

  • 数据规模 N ≤ 1e3，允许 O(n²)；若 n ≤ 300，O(n³) 通常也跑得动，需看具体常数。
  • 元素值域最大到 1e4 —— 求和 / 相乘时记得开 64 位整数。

样例

样例 1

  • 输入：5 2 / 3 1 2 3 / 1 4 / 2 2 4 / 1 5 / 2 1 3 / 1 / 2
  • 输出：4 / 1

解析由校招宝本地引擎整理（依据源站考点标签 / 人工判题标注 / 题面规模信号），非官方题解，仅供思路参考。

本题来源：2026年-华为-04月29号开发岗。

‹ 上一题 全部编程题 下一题 ›
编程算法题为只读内容：无需作答，直接看题与解析 · 本站不提供在线判题 · 解析由校招宝本地引擎整理，非官方题解