---

哈希表+并查集专题(PAT)：

1.找硬币

找硬币

 

2.朋友数

朋友数

 

3.漏掉的数字

漏掉的数字

 

4.危险品装箱

危险品装箱

 

5.哈希

哈希

 

6.期终成绩

期终成绩

 

7.哈希-平均查找时间

哈希-平均查找时间

 

8.集合相似度

集合相似度

 

9.合并集合

合并集合

 

10.森林里的鸟

森林里的鸟

 

11.战争中的城市

战争中的城市

 

12.家产

家产

 

13.社会集群

社会集群

 

AC代码:

1.找硬币

/*
  O(n^2)会爆时间,不能枚举两次
  法1:将数存储在map中,枚举每个数x,判断 m - x是否在map中
  法2:对于每个x,二分查找m - x
*/
# include <bits/stdc++.h>
using namespace std;
unordered_map<int,int> M;
int n,m;
vector<int> ans;

int main (void){
  cin >> n >> m;
  
  for (int i = 1; i <= n; ++i){
    int x;
    cin >> x;
    M[x] ++;
    ans.push_back(x);
  }
  
  sort(ans.begin(),ans.end());
  
  bool flag = false;
  for (int i = 0; i < ans.size() ; ++i){
    int x = ans[i];
    
    // 要先把这个数x从map中摘除掉,防止重复
    M[x] --;
    
    if (M[m - x] >...