魔法商城的免单争夺战
哈希表工作级
🔒 视频讲解去 OJ 刷题 ↗
题目描述
魔法商城每天会举办一场“免单争夺战”：每件商品都有一个能量价格，巫师手中持有固定额度的魔力券。当且仅当存在两件不同的商品，它们的能量价格之和恰好等于魔力券额度时，本次争夺即可免单成功。
请统计在给定的商品价格列表中，有多少对不同的商品（i < j）满足两者价格之和等于目标额度。同一件商品不能与自身配对，下标不同即视为不同的一对。
输入格式
第一行包含两个整数 n 和 target，分别表示商品数量与魔力券额度，满足 1 ≤ n ≤ 10^5，0 ≤ target ≤ 10^9。
第二行包含 n 个整数，表示每件商品的能量价格，数值范围 0 ≤ price ≤ 10^9。
输出格式
输出一个整数，表示价格之和恰好等于 target 的商品对数。
样例
输入 1
5 6 1 5 3 3 2
输出 1
2
说明：(1,5) 与 (3,3) 两对，价格之和均为 6。
题目解析
理解题目
本题是经典两数之和的计数变形：在一个数组中统计有多少对下标不同的元素之和等于目标值。直接二重循环为 O(n^2)，在 n 达到 10^5 时会超时，需要用哈希表把查找补数的过程降到 O(1)。
使用算法
一次遍历 + 哈希计数：维护一个哈希表记录此前出现过的每个价格的次数。遍历到当前价格 x 时，它的补数为 target - x；累加哈希表中补数的出现次数，即得到以当前元素为“较后一项”的配对数，再把 x 自身计入哈希表。整体时间 O(n)。
实现步骤
- 读取 n、target 与价格数组。
- 初始化空哈希表 cnt 与答案 ans = 0。
- 遍历每个价格 x：先令 ans += cnt[target - x]。
- 再把 cnt[x] 自增 1，保证只与之前出现的元素配对，避免重复与自配。
- 输出 ans。
参考代码
def solve():
# 这道题的完整四语言题解已锁定
# 报名科目一冲刺班即可解锁
...
for case in testcases:
print(solve(case))🔒完整四语言代码已锁定
时空复杂度
时间复杂度
O(n)
空间复杂度
O(n)