PAT甲级1048 Find Coins ：[C++题解]哈希表、两个硬币之和为定值

文章目录

• • 题目分析
  • 题目链接

题目分析

来源：acwing
题意:找两个数，和为定值。

分析：本题在各大OJ上几乎都有， 反正在Leetcode上做过。本题有两种常见的解法，一种是双指针，另一种是用哈希表。

这里给出的是哈希表的解法。

给定一些数，遍历之，此时遍历到a[i]，要看a[i]与它前面遍历过的数是否能构成相加等于m。处理完一个数之后要把它加到hash 表中。这里用的hash表用的是unordered_set，去除重复数字。

for(int i = 0 ;i<n; i++){int x; cin >> x;int y = m -x; //找到配对的数if(hash_table.count(y)){放入hash表更新答案，找到最小的一组}else 放入hash表 }

ac代码

#include<bits/stdc++.h> using namespace std; const int N = 1e5+10; int n ,m;int main(){cin >> n >> m;unordered_set<int> S;int v1 =1e9 ,v2; //v1存较小的数，v2存较大的数for(int i = 0; i< n; i++) {int x;cin >> x;int y = m - x;if(S.count(y)){S.insert(x);//x中存较小的一个if(x > y) swap(x, y);//更新答案if( x < v1) v1 = x,v2 = y;}else S.insert(x);}if(v1 == 1e9) cout<<"No Solution"<<endl;else cout<< v1 <<" "<<v2<<endl;}

题目链接

PAT甲级1048 Find Coins
https://www.acwing.com/problem/content/1534/

总结

以上是生活随笔为你收集整理的PAT甲级1048 Find Coins ：[C++题解]哈希表、两个硬币之和为定值的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。