题目描述与示例

题目

给定两个数组 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 开始，则匹配的二元组分别为(0,3)，(1,2)，(2,1)，(3,0)，共计 4 对二元组。

示例二

输入

6
3
1 2 4 4 2 1
1 2 3

输出

解题思路

数组 A 和 B中各个元素的频率我们都需要统计，可以用两个哈希表进行储存，分别记为cnt_A和cnt_B。接下来我们就来统计能构成的二元组的个数。

接下来我们考虑如何计算二元组的数目。某一个数字num在A中出现的次数为cnt_A[num]，存在两种情况：

如果它在B中没有出现，那么能构成的二元组的个数为0
如果它在B中出现过，出现次数为cnt_B[num]，那么基于简单的乘法原理，能构成的二元组个数为cnt_A[num] * cnt_B[num]

以示例二为例子：元素1在数组A中出现了两次，下标分别为0和5，在数组B中出现了一次，下标为0，所以对于元素1可以构成2 * 1 = 2组二元组，分别为(0, 0)和(5, 0)。元素2也可以构成2组二元组，分别为(1, 1)和(4, 1)。所以一共可以构成2 + 2 = 4组二元组。

如果我们是使用计数器Counter()来储存元素频率，上述两种情况其实可以合并。因为如果num不位于cnt_B的键中，我们会得到cnt_B[num] = 0。因此计算cnt_A[num] * cnt_B[num] = 0。

所以我们只需要遍历cnt_A中的所有键num，计算cnt_A[num]*cnt_B[num]的结果并求和即可。

代码

Python

# 题目：2023Q1A-统计匹配的二元组个数
# 分值：200
# 作者：闭着眼睛学数理化
# 算法：哈希表
# 代码看不懂的地方，请直接在群上提问

# 导入collections中的Counter计数器类，使用dict()也可以，但是代码就要多一些判断
from collections import Counter

nA = int(input())
nB = int(input())
cnt_A = Counter(input().split())
cnt_B = Counter(input().split())
# 基于乘法原理，计算能够构成的二元组的个数
print(sum(cnt_A[num] * cnt_B[num] for num in cnt_A))

Java

import java.util.HashMap;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int nA = scanner.nextInt();
        int nB = scanner.nextInt();

        HashMap<Integer, Integer> cnt_A = new HashMap<>();
        HashMap<Integer, Integer> cnt_B = new HashMap<>();

        for (int i = 0; i < nA; i++) {
            int num = scanner.nextInt();
            cnt_A.put(num, cnt_A.getOrDefault(num, 0) + 1);
        }

        for (int i = 0; i < nB; i++) {
            int num = scanner.nextInt();
            cnt_B.put(num, cnt_B.getOrDefault(num, 0) + 1);
        }

        long total = 0;

        for (int num : cnt_A.keySet()) {
            if (cnt_B.containsKey(num)) {
                int countA = cnt_A.get(num);
                int countB = cnt_B.get(num);
                total += (long) countA * countB;
            }
        }

        System.out.println(total);
    }
}

C++

“`C++
#include <iostream>
#include <unordered_map>
#include <vector>

int main() {
int nA, nB;
std::cin >> nA;
std::cin >> nB;

<pre><code>std::unordered_map<int, int> cnt_A;
std::unordered_map<int, int> cnt_B;

for (int i = 0; i < nA; ++i) {
int num;
std::cin >> num;
cnt_A[num]++;
}

for (int i = 0; i < nB; ++i) {
int num;
std::cin >> num;
cnt_B[num]++;
}

long long total = 0;
for (const auto& pair : cnt_A) {
int num = pair.first;
int countA = pair.second;
int countB = cnt_B[num];

total += static_cast<long long>(countA) * countB;
}

std::cout << total << std::endl;

return 0;
</code></pre>

}

“`

时空复杂度

时间复杂度：O(N+M)。需要遍历数组构建哈希表。

空间复杂度：O(N+M)。哈希表所占用空间。

说明

华为OD机试有三道题⽬，第⼀道和第⼆道属于简单或中等题，分值为 100 分，第三道为中等或困难题，分值为 200分，总分为 400 分。

机试分数越⾼评级越⾼，⼯资也就越⾼。

关于华为 OD 机试更加详细的介绍可以查看这篇⽂章：华为OD机考须知

关于机考题目汇总可以看这篇文章：华为OD机试真题 2023 A+B+C+D卷 + 2024新卷（Python&Java&C++）⽬录汇总（每⽇更新）