二分
#include <algorithm>
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int n, m;
int a[N];
bool find(int x, int y) {
int l = 0, r = n - 1;
while (l < r) {
int mid = (l + r) >> 1;
if (a[mid] >= y) {
r = mid;
} else {
l = mid + 1;
}
}
if (a[l] != y) {
return false;
}
if (x != y) {
return true;
}
return a[l] == a[l + 1];
}
int main() {
cin >> n >> m;
for (int i = 0; i < n; i++) {
cin >> a[i];
}
sort(a, a + n);
for (int i = 0; i < n; i++) {
int x = a[i], y = m - a[i];
if (find(x, y)) {
cout << x << " " << y << endl;
return 0;
}
}
puts("No Solution");
return 0;
}
双指针
/*
* Project: Week3
* File Created:Tuesday, January 19th 2021, 6:26:45 pm
* Author: Bug-Free
* Problem:AcWing 1532. 找硬币 双指针
*/
#include <algorithm>
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int n, m;
int a[N];
int main() {
cin >> n >> m;
for (int i = 0; i < n; i++) {
cin >> a[i];
}
sort(a, a + n);
for (int i = 0, j = n - 1; i < j; i++) {
while (i < j && a[i] + a[j] > m) {
j--;
}
if (i < j && a[i] + a[j] == m) {
cout << a[i] << " " << a[j] << endl;
return 0;
}
}
cout << "No Solution" << endl;
return 0;
}
哈希表
/*
* Project: Week3
* File Created:Tuesday, January 19th 2021, 8:33:06 pm
* Author: Bug-Free
* Problem:AcWing 1532. 找硬币 哈希表
*/
#include <algorithm>
#include <iostream>
#include <unordered_set>
using namespace std;
using namespace std;
const int N = 1e5 + 10;
int n, m;
int main() {
cin >> n >> m;
unordered_set<int> hash;
int v1 = 1e4, v2;
for (int i = 0; i < n; i++) {
int a, b;
cin >> a;
b = m - a;
// 如果hash表中存在b
if (hash.count(b)) {
hash.insert(a);
if (a > b) {
swap(a, b);
}
if (a < v1) {
v1 = a, v2 = b;
}
} else {
hash.insert(a);
}
}
if (v1 == 1e4) {
puts("No Solution");
} else {
cout << v1 << " " << v2 << endl;
}
return 0;
}
dalao,我想问一下,hash表不是只建立吗,也没有插值操作,怎么能判断里面是不是有b呢。。。
count(b) 可以判断hash表中是否有b, unordered_set会自动去重, 因此如果hash表中存在b, count(b)=1
hash表没有插值,不就是个空表吗,怎么会有值呢。。。
代码后面有一个else, 会插入a的, 就有值了
!!谢谢大佬 orz