【华为OD机试2023】统计匹配的二元组个数Python
题目描述：
给定两个数组A和B，若数组A的某个元素A[i]与数组B中的某个元素B[j]满足 A[i] == B[j], 则寻找到一个值匹配的二元组(i, j). 请统计在这两个数组A和B中，一共存在多少个这样的二元组。
输入描述：
第一行输入数组A的长度M；第二行输入数组B的长度N；第三行输入数组A的值；第四行输入数组B的值。
1 <= M, N <= 100000
A, B数组中数值的取值均小于100000；
输出描述：
输出匹配的二元组个数。
补充说明：
若不存在相等的值，则输出0. 所采用的算法复杂度需小于O(N^2)，否则会超时。输入数组中允许出现重复数字，一个数字可以匹配多次。
示例1
输入：
5
4
1 2 3 4 5
4 3 2 1
输出：
4
说明：
若下标从0开始，则匹配的二元组分别为(0, 3), (1, 2), (2, 1), (3, 0), 共计4个。
示例2
输入：
6
3
1 2 4 4 2 1
1 2 3
输出：
4
说明：
若下标从0开始，则匹配的二元组分别为(0, 0), (1, 1), (4, 1), (5, 0) 共计4个。
解题思路：
限制了时间复杂度，就不能两层for循环遍历了。考虑到只需要输出匹配二元组的个数，而不要求列出所有匹配二元组，那么可以先把a中数字去重，然后逐个遍历，如果该数字也存在于b中，那么该数字的匹配二元组个数就是a中该数字个数乘以b中该数字个数
m=int(input())
n=int(input())
lst_a=list(map(int,input().split()))
lst_b=list(map(int,input().split()))
sum=0
for num in set(lst_a):
if num in lst_b:
sum+=lst_a.count(num)*lst_b.count(num)
print(sum)
类似资料：