和为给定数

题目描述

给出 $n$ 个整数，问是否存在两个不同位置的数之和等于 $m$ ；存在则输出这对数（小的在前、大的在后，空格分隔），多解时取较小数最小的那对，否则输出 No。 $0<n\le100000$ ，整数范围 $0\sim10^8$ ， $0\le m\le 2^{30}$ 。

输入第一行 $n$ ，第二行 $n$ 个整数，第三行 $m$ 。样例输入为三行：4、2 5 1 4、6；对应输出 1 5。

思路

把数列升序排序，用首尾双指针 $(i,j)$ 夹逼： $a_i+a_j<m$ 时 $a_i$ 与任何数都配不出 $m$ ，左指针右移；和偏大则右指针左移；相等即命中。左端点按从小到大被访问，所以首次命中的数对就是较小数最小的答案。

参考代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-30 01:23
# update_at: 2026-09-30 01:23

import sys


def find_pair(nums: list[int], target: int) -> tuple[int, int] | None:
    """双指针求和为 target 的数对：首个命中即"较小的数更小"的最优解。"""
    i, j = 0, len(nums) - 1
    while i < j:
        total = nums[i] + nums[j]
        if total < target:
            i += 1  # 左端已最小，j 及其左侧都配不出 target，放弃 nums[i]
        elif total > target:
            j -= 1  # 同理放弃 nums[j]
        else:
            return nums[i], nums[j]
    return None


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)
    nums = sorted(next(data) for _ in range(n))  # 排序后双指针才能单调移动
    target = next(data)

    pair = find_pair(nums, target)
    print("No" if pair is None else f"{pair[0]} {pair[1]}")


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-05 06:30
 * update_at: 2026-10-05 06:30
 */
#include <algorithm>
#include <cstdio>
using namespace std;

typedef long long ll;

const int MAXN = 100005;

ll a[MAXN]; // a[1..n] 存放输入的 n 个整数，排序后升序

int main() {
    ll n, m;
    scanf("%lld", &n);
    for (ll i = 1; i <= n; i++) {
        scanf("%lld", &a[i]);
    }
    scanf("%lld", &m);

    // 升序排序后，和偏小就放弃左端，和偏大就放弃右端，
    // 行按左端点从小到大访问，首次命中即"较小的数更小"的最优数对。
    sort(a + 1, a + n + 1);
    ll i = 1;
    ll j = n;
    while (i < j) {
        ll sum = a[i] + a[j];
        if (sum < m) {
            i++; // a[i] 与任何右侧元素都配不出 m，整行放弃
        } else if (sum > m) {
            j--; // 同理整列放弃
        } else {
            printf("%lld %lld\n", a[i], a[j]);
            return 0;
        }
    }
    printf("No\n");
    return 0;
}

目录

题目描述

思路

参考代码