yxc|AcWing 寒假每日一题 2021-01-19 找硬币算法|c++|哈希表|yyds

AcWing 1532. 找硬币（传送门）

文章图片

文章图片

思路分析：
这里给三种思路供参考，前两种思路有些类似，就是实现方式不同
第一种：
先对硬币排序，然后建立一个标记数组，时间复杂度 O(nlogn)
AC代码：

#include using namespace std; const int N = 1e5 + 10; int n, m; int a[N]; int flag[N]; int main() {while (cin >> n >> m) {memset(flag, 0, sizeof(flag)); for (int i = 0; i < n; i++) {cin >> a[i]; flag[a[i]]++; } sort(a, a + n); bool flag2 = false; int v1, v2; for (int i = 0; i < n; i++) {if (flag[m - a[i]]) {v1 = a[i]; v2 = m - a[i]; flag2 = true; break; } } if (flag2 && v1 != v2) cout << v1 << ' ' << v2 << endl; else cout << "No Solution" << endl; } return 0; }

第二种：
双指针，时间复杂度也是 O(nlogn)，双指针一般针对具有单调性的数组，并且大概率是左指针逐渐递增，右指针逐渐递减的
AC代码：

#include using namespace std; const int N = 1e5 + 10; int n, m; int a[N]; int main() {while (cin >> n >> m) {for (int i = 0; i < n; i++) cin >> a[i]; sort(a, a + n); bool flag = false; for (int i = 0, j = n - 1; i < j; i++) {while (a[i] + a[j] > m) j--; if (a[i] + a[j] == m && i != j) {cout << a[i] << ' ' << a[j] << endl; flag = true; break; } } if (!flag) cout << "No Solution" << endl; } return 0; }

第三种：
用 hash表进行查询操作，hash表的查询操作的时间复杂度为 O(1)，整体时间复杂度为 O(n)
【yxc|AcWing 寒假每日一题 2021-01-19 找硬币】AC代码：

#include #define ll long longusing namespace std; int n,m; int main() {while (cin >> n >> m) {unordered_set hash; int v1 = 10000,v2; // v1 只要比 M 的最大值大都可以 for(int i = 0; i> a; int b = m - a; if(hash.count(b)) {if(a > b) swap(a,b); if(a < v1) {v1 = a; v2 = b; } } hash.insert(a); } if(v1 == 10000) cout << "No Solution" << endl; else cout << v1 << ' ' << v2 << endl; } return 0; }