華為OD機試真題——統計匹配的二元組個數（2025A卷：100分）Java/python/JavaScript/C++/C語言/GO六種最佳實現

在這里插入圖片描述

2025 A卷 100分題型

本文涵蓋詳細的問題分析、解題思路、代碼實現、代碼詳解、測試用例以及綜合分析；
并提供Java、python、JavaScript、C++、C語言、GO六種語言的最佳實現方式！

2025華為OD真題目錄+全流程解析/備考攻略/經驗分享

華為OD機試真題《統計匹配的二元組個數》：

- 題目名稱：統計匹配的二元組個數
- - 題目描述
- Java
- - 問題分析
  - 解題思路
  - 代碼實現
  - 代碼詳細解析
  - 示例測試
  - 綜合分析
- python
- - 問題分析
  - 解題思路
  - 代碼實現
  - 代碼詳細解析
  - 示例測試
  - 綜合分析
- JavaScript
- - 問題分析
  - 解題思路
  - 代碼實現
  - 代碼詳細解析
  - 示例測試
  - 綜合分析
- C++
- - 問題分析
  - 解題思路
  - 代碼實現
  - 代碼逐行解析
  - 示例測試
  - 綜合分析
- C語言
- - 問題分析
  - 解題思路
  - 代碼實現
  - 代碼詳細解析
  - 示例測試
  - 綜合分析
- GO
- - 問題分析
  - 解題思路
  - 代碼實現
  - 代碼詳細解析
  - 示例測試
  - 綜合分析
- 更多內容：

題目名稱：統計匹配的二元組個數

知識點：數組、哈希表
時間限制：1秒
空間限制：32MB
限定語言：不限

題目描述

給定兩個數組A和B，統計滿足A[i] == B[j]的二元組(i,j)的總個數。

輸入描述

第一行輸入數組A的長度M
第二行輸入數組B的長度N
第三行輸入數組A的元素（空格分隔）
第四行輸入數組B的元素（空格分隔）

輸出描述
輸出匹配的二元組個數。若不存在匹配，輸出0。

示例1
輸入：

輸出：

示例2
輸入：

6  
3  
1 2 4 4 2 1  
1 2 3

輸出：

Java

問題分析

我們需要統計兩個數組A和B中滿足A[i] == B[j]的二元組(i,j)的總個數。直接遍歷所有可能的組合會導致時間復雜度為O(M*N)，但通過哈希表優化可以將時間復雜度降低到O(M + N)。

解題思路

哈希表統計頻率：遍歷數組A，用哈希表記錄每個元素出現的次數。
遍歷數組B匹配：遍歷數組B，對于每個元素，在哈希表中查找其出現次數并累加。

代碼實現

import java.util.*;
import java.io.*;public class Main {public static void main(String[] args) throws IOException {// 使用BufferedReader讀取輸入，避免Scanner的換行符問題BufferedReader br = new BufferedReader(new InputStreamReader(System.in));// 讀取數組A和B的長度int M = Integer.parseInt(br.readLine());int N = Integer.parseInt(br.readLine());// 讀取數組A的元素并轉換為整型數組String[] aParts = br.readLine().split(" ");int[] a = new int[M];for (int i = 0; i < M; i++) {a[i] = Integer.parseInt(aParts[i]);}// 讀取數組B的元素并轉換為整型數組String[] bParts = br.readLine().split(" ");int[] b = new int[N];for (int i = 0; i < N; i++) {b[i] = Integer.parseInt(bParts[i]);}// 創建哈希表統計數組A中每個元素的出現次數Map<Integer, Integer> countMap = new HashMap<>();for (int num : a) {countMap.put(num, countMap.getOrDefault(num, 0) + 1);}// 遍歷數組B，累加匹配次數int result = 0;for (int num : b) {result += countMap.getOrDefault(num, 0);}// 輸出結果System.out.println(result);}
}

代碼詳細解析

讀取輸入：
- BufferedReader逐行讀取輸入，避免Scanner的換行符問題。
- 前兩行讀取數組A和B的長度M和N。
- 第三行讀取數組A的元素并轉換為整型數組。
- 第四行讀取數組B的元素并轉換為整型數組。
統計數組A的元素頻率：
- 使用HashMap存儲數組A中每個元素及其出現次數。
- countMap.getOrDefault(num, 0)確保元素不存在時返回0。
遍歷數組B計算匹配次數：
- 對數組B中的每個元素，查找其在哈希表中的出現次數。
- 累加所有匹配次數，得到最終結果。

示例測試

示例1輸入：

輸出：

解析：

數組A中每個元素出現1次，數組B中的元素4、3、2、1均能在A中找到，總共有4對。

示例2輸入：

6
3
1 2 4 4 2 1
1 2 3

輸出：

解析：

數組A中1出現2次、2出現2次，數組B中的1和2分別匹配2次，總共有4次。

綜合分析

時間復雜度：
- 統計頻率：O(M)，遍歷數組A一次。
- 匹配計算：O(N)，遍歷數組B一次。
- 總復雜度：O(M + N)，線性時間復雜度。
空間復雜度：
- 哈希表存儲：O(M)，存儲數組A中所有不同元素及其頻率。
優勢：
- 高效性：相比暴力法的O(M*N)，哈希表將復雜度優化到O(M + N)。
- 代碼簡潔：邏輯清晰，易于理解和維護。
適用場景：
- 處理大規模數據時，哈希表方法能顯著提升性能。
- 適用于需要快速查找元素出現次數的場景。

python

問題分析

解題思路

哈希表統計頻率：遍歷數組A，用字典記錄每個元素出現的次數。
遍歷數組B匹配：遍歷數組B，對于每個元素，在字典中查找其出現次數并累加。

代碼實現

def main():import sys# 讀取輸入數據m = int(sys.stdin.readline())       # 讀取數組A的長度n = int(sys.stdin.readline())       # 讀取數組B的長度# 讀取數組A的元素并轉換為整數列表a = list(map(int, sys.stdin.readline().split()))# 驗證數組長度是否匹配輸入值if len(a) != m:print(0)return# 讀取數組B的元素并轉換為整數列表b = list(map(int, sys.stdin.readline().split()))# 驗證數組長度是否匹配輸入值if len(b) != n:print(0)return# 創建字典統計數組A中每個元素的出現次數count_dict = {}for num in a:# 如果元素存在，計數+1；不存在則初始化為0后+1count_dict[num] = count_dict.get(num, 0) + 1# 遍歷數組B，統計總匹配次數total = 0for num in b:# 從字典中獲取該元素的出現次數（默認0次）total += count_dict.get(num, 0)print(total)if __name__ == "__main__":main()

代碼詳細解析

輸入處理：
- sys.stdin.readline() 逐行讀取輸入，避免緩沖區問題
- m 和 n 分別讀取數組A和B的長度
- a = list(map(...)) 將輸入行分割為字符串列表并轉換為整數列表
- 驗證數組長度是否與輸入值一致，防止數據錯誤
頻率統計字典：
- 創建空字典 count_dict 存儲元素頻率
- count_dict.get(num, 0) 是字典的安全訪問方法：
  - 當元素存在時返回當前計數值
  - 不存在時返回默認值0
- 遍歷數組A時，每個元素計數+1
匹配計算：
- 遍歷數組B的每個元素
- count_dict.get(num, 0) 獲取該元素在A中的出現次數
- 所有匹配次數累加到total
邊界處理：
- 數組長度驗證防止數據格式錯誤
- 不存在的元素自動按0次處理

示例測試

示例1輸入：

輸出：

解析：

A中每個元素出現1次
B中的4、3、2、1均能在A中找到
總匹配次數 = 1+1+1+1 = 4

示例2輸入：

6
3
1 2 4 4 2 1
1 2 3

輸出：

解析：

A中1出現2次，2出現2次，4出現2次
B中的1匹配2次，2匹配2次，3匹配0次
總匹配次數 = 2+2+0 = 4

綜合分析

時間復雜度：
- 統計頻率：O(M)，遍歷數組A一次
- 匹配計算：O(N)，遍歷數組B一次
- 總復雜度：O(M + N)，線性時間復雜度
空間復雜度：
- 字典存儲：最差O(M)（所有元素不同時）
- 輸入存儲：O(M + N) 存儲兩個數組
性能優勢：
- 相比暴力法的O(M*N)，效率提升數百倍
- 例如當M=N=10^{5時，暴力法需10}10次運算（不可行），而哈希法僅需2*10^5次
適用場景：
- 大規模數據處理（如M=1e6, N=1e6）
- 需要頻繁查詢元素出現次數的場景
- 元素取值范圍較大的情況（哈希表不依賴連續空間）
Python特性利用：
- 字典的get()方法簡化了"存在性檢查+默認值"邏輯
- map()函數高效處理類型轉換
- 動態列表自動處理變長數據
擴展性：
- 支持非整數類型（只需可哈希）
- 可輕松修改為統計三元組、四元組等
- 適用于分布式計算（分塊統計頻率后合并）

JavaScript

問題分析

我們需要統計兩個數組 A 和 B 中滿足 A[i] == B[j] 的二元組 (i, j) 的總個數。直接遍歷所有組合的時間復雜度為 O(M*N)，但通過哈希表優化可以將時間復雜度降低到 O(M + N)。

解題思路

哈希表統計頻率：遍歷數組 A，用哈希表記錄每個元素出現的次數。
遍歷數組 B 匹配：遍歷數組 B，對于每個元素，在哈希表中查找其出現次數并累加。

代碼實現

const readline = require('readline');const rl = readline.createInterface({input: process.stdin,output: process.stdout,terminal: false
});// 輸入處理邏輯
let lineCount = 0;
let M, N, A, B;rl.on('line', (line) => {switch (lineCount) {case 0: // 讀取數組A的長度MM = parseInt(line.trim());break;case 1: // 讀取數組B的長度NN = parseInt(line.trim());break;case 2: // 讀取數組A的元素A = line.trim().split(/\s+/).map(Number);if (A.length !== M) {console.log(0);process.exit();}break;case 3: // 讀取數組B的元素B = line.trim().split(/\s+/).map(Number);if (B.length !== N) {console.log(0);process.exit();}processInput(); // 處理輸入數據break;}lineCount++;
});function processInput() {// 統計A中元素的頻率const countMap = {};for (const num of A) {countMap[num] = (countMap[num] || 0) + 1;}// 計算總匹配次數let total = 0;for (const num of B) {total += countMap[num] || 0;}console.log(total);rl.close();
}

代碼詳細解析

輸入處理：

const rl = readline.createInterface(...) // 創建輸入接口
rl.on('line', ...)                       // 監聽每一行輸入

使用 Node.js 的 readline 模塊逐行讀取輸入
通過 switch 語句處理不同行的輸入內容

數組驗證：

if (A.length !== M) { ... } // 驗證數組A長度
if (B.length !== N) { ... } // 驗證數組B長度

檢查輸入數組長度是否與聲明的長度一致
發現不一致立即輸出 0 并退出

哈希表統計：
```
const countMap = {};
for (const num of A) {countMap[num] = (countMap[num] || 0) + 1;
}
```
- 使用普通對象作為哈希表
- (countMap[num] || 0) 實現類似 Python 的 get() 方法
匹配計算：
```
for (const num of B) {total += countMap[num] || 0;
}
```
- 遍歷數組 B 的每個元素
- 累加哈希表中對應元素的出現次數

示例測試

示例1輸入：

輸出：

解析：

A 中每個元素出現1次
B 中的 4、3、2、1 均能在 A 中找到
總匹配次數 = 1+1+1+1 = 4

示例2輸入：

6
3
1 2 4 4 2 1
1 2 3

輸出：

解析：

A 中 1 出現2次，2 出現2次
B 中的 1 匹配2次，2 匹配2次
總匹配次數 = 2+2+0 = 4

綜合分析

時間復雜度：
- 統計頻率：O(M)，遍歷數組A一次
- 匹配計算：O(N)，遍歷數組B一次
- 總復雜度：O(M + N)，線性時間復雜度
空間復雜度：
- 哈希表存儲：最差 O(M)（所有元素不同時）
- 輸入存儲：O(M + N) 存儲兩個數組
性能優勢：
- 相比暴力法 O(M*N) 的復雜度，效率提升數百倍
- 例如當 M=N=10^5 時，暴力法需要 1e10 次運算（不可行），而哈希法僅需 2e5 次
JavaScript 特性利用：
- 對象動態屬性實現哈希表
- || 運算符實現默認值
- map(Number) 快速類型轉換
擴展性：
- 支持非數字類型（需可哈希）
- 可輕松修改為統計三元組等復雜場景
- 適用于瀏覽器和 Node.js 雙環境

C++

問題分析

給定兩個數組A和B，統計滿足A[i] == B[j]的二元組(i,j)的總個數。直接遍歷所有組合的時間復雜度為O(M*N)，但通過哈希表優化可以將時間復雜度降低到O(M + N)。

解題思路

哈希表統計頻率：遍歷數組A，用unordered_map記錄每個元素出現的次數。
遍歷數組B匹配：遍歷數組B，對于每個元素，在哈希表中查找其出現次數并累加。

代碼實現

#include <iostream>
#include <vector>
#include <sstream>
#include <unordered_map>using namespace std;int main() {int M, N;// 讀取數組A和B的長度cin >> M >> N;// 清除輸入緩沖區中的換行符cin.ignore(numeric_limits<streamsize>::max(), '\n');// 讀取數組A的元素string lineA;getline(cin, lineA);vector<int> A;stringstream ssA(lineA);int num;while (ssA >> num) {A.push_back(num);}// 驗證數組A長度if (A.size() != M) {cout << 0 << endl;return 0;}// 讀取數組B的元素string lineB;getline(cin, lineB);vector<int> B;stringstream ssB(lineB);while (ssB >> num) {B.push_back(num);}// 驗證數組B長度if (B.size() != N) {cout << 0 << endl;return 0;}// 統計數組A中每個元素的出現次數unordered_map<int, int> countMap;for (int num : A) {countMap[num]++;}// 遍歷數組B統計總匹配次數int total = 0;for (int num : B) {total += countMap[num]; // 若不存在則返回0}cout << total << endl;return 0;
}

代碼逐行解析

輸入處理：
```
cin >> M >> N;  // 讀取數組A和B的長度
cin.ignore(...); // 清除緩沖區中的換行符
getline(cin, lineA); // 讀取數組A的元素行
```
- 使用cin讀取數組長度后，必須用cin.ignore()清除緩沖區殘留的換行符
- getline按行讀取數組元素，避免空格和換行符干擾

數組元素解析：

stringstream ssA(lineA); // 將字符串轉換為流
while (ssA >> num) { ... } // 逐個讀取整數

stringstream將字符串按空格分割為整數流
vector動態存儲數組元素

哈希表統計：
```
unordered_map<int, int> countMap;
for (int num : A) { countMap[num]++; }
```
- unordered_map以O(1)時間復雜度實現鍵值查找
- 遍歷數組A時，每個元素在哈希表中計數+1
匹配次數計算：
```
total += countMap[num]; // 若不存在則返回0
```
- 直接通過countMap[num]訪問次數，未找到時返回0
- 遍歷數組B時累加所有匹配次數

示例測試

示例1輸入：

5 4
1 2 3 4 5
4 3 2 1

輸出：

解析：

A中的每個元素出現1次
B中的4、3、2、1均能在A中找到，總匹配次數=1+1+1+1=4

示例2輸入：

6 3
1 2 4 4 2 1
1 2 3

輸出：

解析：

A中1出現2次，2出現2次
B中的1匹配2次，2匹配2次，3匹配0次
總匹配次數=2+2+0=4

綜合分析

時間復雜度：
- 統計頻率：O(M)，遍歷數組A一次
- 匹配計算：O(N)，遍歷數組B一次
- 總復雜度：O(M + N)，線性時間復雜度
空間復雜度：
- 哈希表存儲：最差O(M)（所有元素不同時）
- 輸入存儲：O(M + N) 存儲兩個數組
性能優勢：
- 相比暴力法的O(M*N)，效率提升數百倍
- 例如當M=N=10^5時，暴力法需要1e10次運算（不可行），哈希法僅需2e5次
C++特性利用：
- unordered_map實現哈希表，平均O(1)查詢時間
- stringstream處理復雜的輸入分割邏輯
- vector動態數組自動管理內存
擴展性：
- 支持非整型數據（需自定義哈希函數）
- 可輕松修改為統計三元組等復雜場景
- 適用于高性能計算場景（如嵌入式系統）

C語言

問題分析

我們需要統計兩個數組A和B中滿足A[i] == B[j]的二元組(i,j)的總個數。直接遍歷所有組合的時間復雜度為O(M*N)，但通過哈希表優化可以將時間復雜度降低到O(M + N)。

解題思路

哈希表統計頻率：遍歷數組A，使用哈希表記錄每個元素出現的次數。
遍歷數組B匹配：遍歷數組B，對于每個元素，在哈希表中查找其出現次數并累加。

代碼實現

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>#define HASH_SIZE 10007 // 哈希表大小，質數減少沖突typedef struct HashNode {int key;           // 存儲元素值int value;         // 存儲出現次數struct HashNode *next;
} HashNode;typedef struct {HashNode **buckets; // 哈希桶數組int size;           // 哈希表大小
} HashMap;// 創建哈希表
HashMap* createHashMap(int size) {HashMap *map = (HashMap*)malloc(sizeof(HashMap));map->size = size;map->buckets = (HashNode**)calloc(size, sizeof(HashNode*)); // 初始化為空指針return map;
}// 插入元素到哈希表
void put(HashMap *map, int key) {int index = abs(key) % map->size; // 哈希函數：絕對值取模處理負數HashNode *current = map->buckets[index];// 遍歷鏈表，查找是否已存在該鍵while (current != NULL) {if (current->key == key) {current->value++; // 存在則計數加1return;}current = current->next;}// 創建新節點插入鏈表頭部HashNode *newNode = (HashNode*)malloc(sizeof(HashNode));newNode->key = key;newNode->value = 1;newNode->next = map->buckets[index];map->buckets[index] = newNode;
}// 查詢元素出現次數
int get(HashMap *map, int key) {int index = abs(key) % map->size;HashNode *current = map->buckets[index];// 遍歷鏈表查找鍵while (current != NULL) {if (current->key == key) {return current->value;}current = current->next;}return 0; // 未找到返回0
}// 釋放哈希表內存
void freeHashMap(HashMap *map) {for (int i = 0; i < map->size; i++) {HashNode *current = map->buckets[i];while (current != NULL) {HashNode *temp = current;current = current->next;free(temp);}}free(map->buckets);free(map);
}int main() {char line[1000000];int M, N;// 讀取數組A和B的長度fgets(line, sizeof(line), stdin);sscanf(line, "%d", &M);fgets(line, sizeof(line), stdin);sscanf(line, "%d", &N);// 讀取數組A的元素fgets(line, sizeof(line), stdin);int *A = (int*)malloc(M * sizeof(int));int count = 0;char *token = strtok(line, " ");while (token != NULL && count < M) {A[count++] = atoi(token);token = strtok(NULL, " ");}if (count != M) { // 驗證元素數量是否正確printf("0\n");free(A);return 0;}// 讀取數組B的元素fgets(line, sizeof(line), stdin);int *B = (int*)malloc(N * sizeof(int));count = 0;token = strtok(line, " ");while (token != NULL && count < N) {B[count++] = atoi(token);token = strtok(NULL, " ");}if (count != N) { // 驗證元素數量是否正確printf("0\n");free(A);free(B);return 0;}// 創建哈希表并統計A的頻次HashMap *map = createHashMap(HASH_SIZE);for (int i = 0; i < M; i++) {put(map, A[i]);}// 遍歷B數組累加匹配次數int total = 0;for (int i = 0; i < N; i++) {total += get(map, B[i]);}printf("%d\n", total);// 釋放內存freeHashMap(map);free(A);free(B);return 0;
}

代碼詳細解析

哈希表結構定義：
- HashNode：鏈表節點，存儲鍵、值和下一個節點的指針。
- HashMap：哈希表結構，包含桶數組和大小。
哈希表操作：
- createHashMap：分配內存，初始化桶數組。
- put：插入元素。若鍵存在，計數加1；否則新建節點插入鏈表頭部。
- get：查詢鍵的出現次數，遍歷鏈表查找。
- freeHashMap：釋放哈希表所有節點內存。
輸入處理：
- 使用fgets逐行讀取輸入，strtok分割字符串。
- 驗證數組長度是否與輸入一致，避免數據錯誤。
核心邏輯：
- 遍歷數組A，通過哈希表統計頻次。
- 遍歷數組B，累加哈希表中的頻次，得到總匹配數。

示例測試

示例1輸入：

輸出：

解析：

A中每個元素出現1次。
B中4、3、2、1各匹配1次，總對數4。

示例2輸入：

6
3
1 2 4 4 2 1
1 2 3

輸出：

解析：

A中1出現2次，2出現2次。
B中1和2各匹配2次，總對數4。

綜合分析

時間復雜度：
- 統計頻率：O(M)，遍歷數組A一次。
- 匹配計算：O(N)，遍歷數組B一次。
- 總復雜度：O(M + N)，線性時間復雜度。
空間復雜度：
- 哈希表：O(M)，存儲數組A元素的頻次。
- 輸入數組：O(M + N)，存儲原始數據。
優勢：
- 高效性：避免暴力法的O(M*N)復雜度。
- 通用性：支持任意整數（包括負數），哈希函數處理簡單。
適用場景：
- 大規模數據，如M和N達到10^5級別。
- 需要快速統計元素頻次并匹配的場景。

GO

問題分析

解題思路

哈希表統計頻率：遍歷數組A，用map記錄每個元素出現的次數。
遍歷數組B匹配：遍歷數組B，對于每個元素，在哈希表中查找其出現次數并累加。

代碼實現

package mainimport ("bufio""fmt""os""strconv""strings"
)func main() {// 創建輸入掃描器scanner := bufio.NewScanner(os.Stdin)// 讀取數組A的長度Mscanner.Scan()M, _ := strconv.Atoi(scanner.Text())// 讀取數組B的長度Nscanner.Scan()N, _ := strconv.Atoi(scanner.Text())// 讀取數組A的元素scanner.Scan()aLine := scanner.Text()A := strings.Fields(aLine)if len(A) != M {fmt.Println(0)return}// 讀取數組B的元素scanner.Scan()bLine := scanner.Text()B := strings.Fields(bLine)if len(B) != N {fmt.Println(0)return}// 統計數組A中元素的出現次數countMap := make(map[string]int)for _, numStr := range A {countMap[numStr]++}// 計算總匹配次數total := 0for _, numStr := range B {total += countMap[numStr]}fmt.Println(total)
}

代碼詳細解析

輸入處理：
- bufio.Scanner：創建輸入掃描器逐行讀取數據。
- strconv.Atoi：將字符串轉換為整數，用于讀取數組長度。
- strings.Fields：按空格分割字符串，處理數組元素。

數組驗證：

if len(A) != M { ... }  // 驗證數組A長度
if len(B) != N { ... }  // 驗證數組B長度

檢查分割后的元素數量是否與聲明的長度一致。

哈希表統計：
```
countMap := make(map[string]int)
for _, numStr := range A {countMap[numStr]++
}
```
- 使用字符串直接作為鍵（避免類型轉換開銷）。
- 遍歷數組A時，每個字符串元素計數+1。
匹配計算：
```
for _, numStr := range B {total += countMap[numStr]
}
```
- 遍歷數組B的每個元素，累加哈希表中的出現次數。
- 未找到時返回默認值0。

示例測試

示例1輸入：

輸出：

解析：

A中每個元素出現1次。
B中的"4"、"3"、"2"、"1"均匹配1次，總對數4。

示例2輸入：

6
3
1 2 4 4 2 1
1 2 3

輸出：

解析：

A中"1"出現2次，"2"出現2次。
B中的"1"匹配2次，"2"匹配2次，總對數4。

綜合分析

時間復雜度：
- 統計頻率：O(M)，遍歷數組A一次。
- 匹配計算：O(N)，遍歷數組B一次。
- 總復雜度：O(M + N)，線性時間復雜度。
空間復雜度：
- 哈希表存儲：O(M)，存儲數組A元素的字符串形式。
- 輸入存儲：O(M + N)，存儲原始字符串數據。
性能優化：
- 直接使用字符串鍵：避免多次類型轉換。
- 哈希表快速查找：Go的map實現基于哈希表，平均O(1)查詢時間。
適用場景：
- 適用于大規模數據（如M=1e6, N=1e6）。
- 需要快速統計元素出現次數的場景。
- 元素包含非數字字符的場景（如"apple"）。
擴展性：
- 支持任意可哈希類型（如結構體）。
- 可輕松修改為統計三元組、四元組等。