【例56.1】 和为给定数

解题思路

升序排序，双指针l、r从两端向中间移动。和小于m增l，和大于m减r，相等输出当前对并结束。

正确性说明

和过小则当前最小数与任何更小右端配对也不足，可排除它；和过大同理排除当前最大数。不丢合法解，且l从小到大推进，首解满足优先规则。

易错点

必须两个不同位置，循环条件l<r；首个匹配较小数最小。

复杂度

时间O(n log n)，空间O(n)。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<long long> a(n);
    for (auto &x : a)
        cin >> x;
    long long m;
    cin >> m;
    sort(a.begin(), a.end());
    int l = 0, r = n - 1;
    while (l < r) {
        long long sum = a[l] + a[r];
        if (sum == m) {
            cout << a[l] << " " << a[r] << "\n";
            return 0;
        }
        if (sum < m)
            l++;
        else
            r--;
    }
    cout << "No\n";
    return 0;
}