输入输出样例 #1
输入 #1
3 5
4 2 3
3 1 5 4 6
输出 #1
2
说明/提示
样例解释
样例 1 中，4、3 在数组 A 与 B 中均出现。

数据范围
对于 40% 的数据，保证 1≤ n,m ≤ 1000。

对于 100% 的数据，保证 1 ≤ n,m ≤ 10^5，1 ≤ a_i,b_i ≤ 10^9。

解题思路：
方法一：
采用二分查找

1.1.1方法：
遍历数组A
每次用二分查找搜索数组B中有没有数组A中的数
统计后输出
1.1.2样例做法：
在B数组中寻找4，发现B数组中有4，count加1；
在B数组中寻找2，发现B数组中没有2，count不变；
在B数组中寻找3，发现B数组中有3，count加1；
最终count = 2，输出结果
1.2.1代码：
AC 记录：https://www.luogu.com.cn/record/280812283

#include<bits/stdc++.h>
using namespace std;
int main() {
int n,m;
scanf(“%d%d”,&n,&m);//读入
int a[n+1],b[m+1],cnt=0;//cnt存储最终结果
for(int i=1;i<=n;i++) scanf(“%d”,&a[i]);//输入A数组
for(int i=1;i<=m;i++) scanf(“%d”,&b[i]);//输入B数组
sort(a+1,a+n+1);//排序
sort(b+1,b+m+1);//二分只针对于有序数组
for(int i=1;i<=m;i++) {//枚举数组
int l=1,r=n;//l为左边界，r为右边界
while(l<=r) {//二分查找
int mid=(l+r)/2;//查找中间值
if(a[mid]>=b[i]) r=mid-1;
else l=mid+1;
}
if(a[l]==b[i]) cnt++;//更新cnt
}
printf(“%d”,cnt);//输出结果
return 0;
}
方法二：
采用STL解题

2.1.1什么是STL：
STL是一套内置的通用工具库，核心组成如下：

容器：存储数据的结构。

vector（动态数组）、map（键值对）、set（唯一元素）、list（链表）等。

迭代器：类似指针，用于遍历容器（如 begin()、end()）。

算法：操作容器的函数。

sort()（排序）、find()（查找）、copy()（复制）等。

本题主要使用map

2.1.2map基础使用方法：
操作类别 函数/方式 示例代码 说明
声明 std::map<KeyType, ValueType> std::map<std::string, int> ages; 按键自动升序排列
插入 [] 运算符 ages[“Alice”] = 25; 键不存在则插入，存在则覆盖
insert ages.insert({“Bob”, 30}); 键已存在时会忽略插入
访问 [] 运算符 ages[“Alice”]; 不安全：键不存在会创建默认值
at() 函数 ages.at(“Bob”); 安全：键不存在抛出 std::out_of_range
查找 find() auto it = ages.find(“Bob”); 返回迭代器，若不存在返回 end()
检查存在 count() if (ages.count(“Bob”)) 存在返回 1，不存在返回 0
删除 erase() ages.erase(“Alice”); 按键值删除
大小 size() int len = ages.size(); 返回键值对个数
判空 empty() if (ages.empty()) 无元素时返回 true
遍历 范围 for for (auto &p : ages) p.first 为键，p.second 为值
清空 clear() ages.clear(); 删除所有元素
2.2.1解题方法
将数字作为键，将是否出现过作为值，一一对应；
在存入A数组时修改值；
在输入B数组是判断是否出现过此数，并修改count；
输出count
2.3.1代码
AC 记录 : https://www.luogu.com.cn/record/273884639

#include<bits/stdc++.h>
using namespace std;
unordered_map<int,bool>mp;
int main() {
int n,m;
cin>>n>>m;//输入
int a[n+1],b[m+1],cnt=0;
for(int i=1;i<=n;i++) {
cin>>a[i];
mp[a[i]]=1;//将a[i]标记为true
}
for(int i=1;i<=m;i++) {
cin>>b[i];//输入B数组中的数
if(mp[b[i]]) cnt++;//判断此数是否在A数组中出现过，并修改cnt的值
}
cout<<cnt;//输出结果
return 0;
}