题目描述

二分 $O(nlogn)$
先排序，然后枚举第一枚硬币，二分查找第二枚硬币

哈希表 $O(n)$

用哈希表存所有硬币的出现次数
然后枚举第一枚硬币，判断第二枚硬币是否存在

注意在枚举时需要处理第一枚硬币和第二枚硬币相等的情况

算法1

(二分) $O(nlogn)$

C++ 代码

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
int n, m;
int c[N];
bool find(int a, int b)
{
    int l = 0, r = n - 1;
    while (l < r)
    {
        int mid = l + r >> 1;
        if (c[mid] >= b) r = mid;
        else l = mid + 1;
    }
    if (c[l] != b) return false;
    if (a != b) return true;
    return c[l] == c[l + 1];
}
int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i ++) cin >> c[i];
    sort(c, c + n);
    for (int i = 0; i < n; i ++)
    {
        int a = c[i], b = m - c[i];
        if (find(a, b))
        {
            cout << a << " " << b;
            return 0;
        }
    }
    puts("No Solution");
}

算法2

(哈希表) $O(n)$

C++ 代码

#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;
const int N = 1e5 + 10;
unordered_map<int, int> q;
int n, m, x = 2e9, y;
int c[N];
int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i ++) cin >> c[i], q[c[i]] ++;
    bool flag = false;
    for (int i = 0; i < n; i ++)
    {
        int a = c[i], b = m - c[i];
        if (a > b) continue;
        if (a != b && q[b] >= 1 || a == b && q[b] >= 2)
        {
            flag = true;
            if (x > a) x = a, y = b;
        }
    }
    if (flag) cout << x << " " << y;
    else puts("No Solution");
}