P18（ACWing笔记）

法一 ： 哈希法

#include <iostream>
#include <algorithm>
#include <unordered_set>

using namespace std;

const int INF = 10000;

int main () {
    unordered_set<int> hash;
    int n, m;
    scanf("%d%d", &n, &m); //n是是数的个数， m是要凑得值
    int v1 = INF, v2; //求得是v1和v2较小值的最小值 ，开始可以将v1设置成∞，表示不存在

    for (int i = 0; i < n; i ++) {
        int a;
        scanf("%d", &a); // 每次读入当前数
        int b = m - a; // 另一个数是m - a  
        // hash.insert(a);  // !!!!!!这样是错的！！！！！
        if (hash.count(b)) { // 在哈希表中判断是否存在另一个数
            hash.insert(a); //将每个数插入哈希表中，交换前插入
            if (a > b) swap(a,b);  // 取v1为小的
            if (a < v1) v1 = a, v2 = b; //！！！注意：这里的if(a < v1) 是不能少的，是为了满足题目中《如果答案不唯一，则输出 V1 最小的解。》
        }
        else hash.insert(a); //将每个数插入哈希表中(不管什么情况都要插入)
    }

    if (v1 == INF) puts("No Solution");
    else printf("%d %d\n",v1, v2);
    return 0;

}

法二 ： 双指针

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010;
int n, m;
int w[N];

int main () {

    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i ++) scanf("%d", &w[i]);
    sort(w, w + n);
    for (int i = 0, j = n - 1; i < n; i ++) {
        while (i < j && w[i] + w[j] > m) j --;
        if (i < j && w[i] + w[j] == m) {
            printf("%d %d\n", w[i], w[j]);
            return 0; // 找到了，在这里就要return
        }
    }
    puts("No Solution");
    return 0;
}