算法思维 · 配对

是否存在两数之和

经典的面试热身题。i 遍历每个元素，j 从 i+1 开始，这样永远不会把一个数和它自己配对，再检查 a[i] + a[j] == T。

一句话答案i 遍历每个元素，j 从 i+1 开始，这样同一个数不会和自己配对；只要有一对之和等于 T 就输出 yes，N ≤ 100 时双层循环足够快。

题目

输入: 第一行 N（1 ≤ N ≤ 100）；第二行 N 个整数；第三行目标 T。

输出: 若存在两个不同的数之和为 T 输出 yes，否则输出 no。

样例：

输入	输出
`4 1 2 3 4 5`	`yes`
`3 1 2 3 7`	`no`
`5 10 20 30 40 50 60`	`yes`

你的解答

main.cpp — 你的解答

「运行我的输入」用的自定义输入

判题在浏览器本地运行。死循环会在 3 秒后被自动中断 —— 但还是确保每个循环都有出口。代码随打随存。

卡住了？提示

提示 1 — 是不同的下标，不是不同的值

用两个下标 i 和 j，且 j > i。这保证是两个不同的位置 —— 所以目标为 6 时 [3, 3] 也算（位置不同），通常这类题说的「两个数」就是指两个不同位置。

提示 2 — 一知道就停

你不需要每一对都试 —— 一旦找到一对就输出 yes 结束。如果循环跑完都没匹配，就输出 no。用 bool 标志避免重复输出。

题解（先自己试试！）

#include <iostream>
using namespace std;

int main() {
    int n, t;
    cin >> n;
    int a[105];
    for (int i = 0; i < n; i++) cin >> a[i];
    cin >> t;
    bool ok = false;
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++)
            if (a[i] + a[j] == t) ok = true;
    cout << (ok ? "yes" : "no") << endl;
    return 0;
}

真正的面试会要求返回下标，或希望用哈希表做到 O(N) —— 但 O(N²) 版本是地基。下一关：第二大的数沿用了「边扫边记」的思路。

深度解析

为什么这样做对

「枚举所有组合」最小的完整例子就是找一对：两个下标、一个不等式保证它们不同、一次比较。你以后见到的每个 O(N²) 算法都是这个形状放大。

代价

O(N²) 时间（N=100 时一万次比较，瞬间完成），数组占 O(N) 空间。可以提前退出，但最坏情况仍要扫完。

常见错法

内层 j 从 0 开始而不是 i+1，元素就会和自己配对 —— 单个 [5]、目标 10 也会答 yes。
在循环里打印：你会输出好几次 yes，而 no 的情况一行都没有，判题直接判错。

下一步

改成要求返回下标，然后排序用双指针 —— 同一个问题做到 O(N log N)。第二大的数沿用了「边扫边记」的习惯。

记住这两句

j 从 i+1 开始：位置不同，同一个元素不会用两次。
先判断、最后只打印一次 —— 在搜索循环里打印会让输出翻倍。

🐞 这段是错的 —— 点开,亲手让它挂一次

在循环里打印 —— 好几行 yes，而 no 的情况一行都不输出

#include <iostream>
using namespace std;

int main() {
    int n, t;
    cin >> n;
    int a[105];
    for (int i = 0; i < n; i++) cin >> a[i];
    cin >> t;
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++)
            if (a[i] + a[j] == t) cout << "yes" << endl;   // prints per match
    return 0;
}