G5022 [GESP202603 五级] 找数 题解

知识点：集合、查找、计数。

解题思路

将第一组数字放入哈希集合，随后逐个检查第二组数字是否存在于集合中，存在则累计。

为什么正确

集合完整表示第一组可被找到的值，每个查询单独判断并贡献对应次数。

易错点

第一组重复数字不增加种类；第二组每次出现按题目查询次数分别统计。

复杂度

平均时间O(n+m)，空间O(n)。

参考代码（C++17）

#include<bits/stdc++.h>

using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m;
    cin>>n>>m;
    unordered_set<int>s;
    for(int i=0;i<n;i++) {
        int x;
        cin>>x;
        s.insert(x);
    }
    int ans=0;
    for(int i=0;i<m;i++) {
        int x;
        cin>>x;
        ans+=s.count(x);
    }
    cout<<ans;
}

说明

本题解为配套教学整理，非官方题解。复杂度按本页参考实现计算，题库使用6个自行生成的测试点。