华为OD机试Java题解：统计匹配的二元组个数（题号：2025A卷）

最新华为OD机试

真题目录：点击查看目录
华为OD面试真题精选：点击立即查看

本题与2023年A卷基本一致：

https://blog.csdn.net/banxia_frontend/article/details/133105425

题目描述

给定两个数组A和B，若数组A的某个元素A[i]与数组B中某个元素B[j]满足 A[i] == B[j]，则寻找到一个值匹配的二元组(i,j)。 请统计在这两个数组A和B中，一共存在多少个这样的二元组。

输入描述

备注： 若不存在相等的值，则输出0。 所采用的算法复杂度需小于O(N^2),否则会超时。 输入数组中允许出现重复数字，一个数字可以匹配多次。

输出描述

输出匹配的二元组个数

示例1

输入

5
4
1 2 3 4 5
4 3 2 1

输出

4

示例2

输入

6
3
1 2 4 4 2 1
1 2 3

输出

4

示例3

输入

4
1
1 2 3 4
1

输出

1

示例4

输入

6
3
1 1 2 2 4 5
2 2 4

输出

5

解题思路

本题要求统计在两个数组 A 和 B 中，所有匹配的二元组 (i, j)，即 A[i] == B[j] 的组合。由于直接使用暴力算法会导致时间复杂度达到 O(N^2)，我们需要通过优化来降低时间复杂度。

1. 暴力算法的不足

直接使用暴力算法遍历数组 A 和 B 中的每一个元素对，检查 A[i] == B[j] 是否成立，显然会导致 O(m * n) 的时间复杂度（其中 m 和 n 分别是数组 A 和 B 的长度）。这种方式在数组长度较大时，效率非常低，容易超时。

<

作者：算法大师