两数之和

题意

给定整数数组 nums 和整数 target，找出两个不同下标 i、j，使得 nums[i] + nums[j] = target，并返回这两个下标。

题目保证答案唯一，因此找到第一组合法下标后即可返回。LeetCode 使用函数签名提交，不需要自行读取标准输入。

思路

最直接的办法是枚举所有满足 i < j 的下标对，逐一检查两数之和：

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/**
 * 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-07-28 18:13
 * update_at: 2026-07-28 18:15
 */
// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 20;

int n, target;
int nums[MAXN];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> target;
    for (int i = 0; i < n; i++) {
        cin >> nums[i];
    }

    // 直接枚举所有 i < j 的下标对，只适合小数据。
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (nums[i] + nums[j] == target) {
                cout << i << ' ' << j << '\n';
                return 0;
            }
        }
    }

    return 0;
}

这种做法不会漏掉任何下标对，但需要检查 $O(n^2)$ 个候选，无法满足进阶要求。

优化的关键是：扫描到当前值 value 时，只需知道它的补数 target - value 是否在前面出现过。用字典 index_by_value 保存“已经扫描过的值到下标”的映射，就能平均 $O(1)$ 完成一次查找。

代码必须先查询补数，再记录当前值。这样字典中只有当前下标之前的元素，不会把同一个位置使用两次；对于 [3, 3] 这样的重复值，第一个 3 会先被记录，扫描到第二个 3 时便能正确返回两个不同下标。

若唯一答案的下标为 $p < q$ ，扫描到 $q$ 时，nums[p] 已经存入字典，并且恰好等于 target - nums[q]，所以算法一定会找到答案。返回的两个下标对应的值之和等于目标值，因此返回结果也一定合法。

Python 中，enumerate(nums) 同时取得下标和值；complement in index_by_value 利用字典的平均 $O(1)$ 成员查询。

代码

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/**
 * 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-07-28 18:13
 * update_at: 2026-07-28 18:15
 */
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 10005;

int n, target;
int nums[MAXN];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> target;
    for (int i = 0; i < n; i++) {
        cin >> nums[i];
    }

    unordered_map<int, int> idx;
    for (int i = 0; i < n; i++) {
        int complement = target - nums[i];
        if (auto it = idx.find(complement); it != idx.end()) {
            cout << it->second << ' ' << i << '\n';
            return 0;
        }
        idx[nums[i]] = i;
    }

    return 0;
}

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#!/usr/bin/env python3
from typing import List


class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        index_by_value: dict[int, int] = {}

        for index, value in enumerate(nums):
            complement = target - value
            if complement in index_by_value:
                return [index_by_value[complement], index]
            index_by_value[value] = index

        raise ValueError("题目保证存在唯一答案")


def main() -> None:
    """本地验证适配层；提交 LeetCode 时只保留 Solution 类即可。"""

    n, target = map(int, input().split())
    nums = list(map(int, input().split()))
    if len(nums) != n:
        raise ValueError("数组长度与 n 不一致")

    answer = Solution().twoSum(nums, target)
    print(*answer)


if __name__ == "__main__":
    main()

另一种思路是排序后双指针：先对数组排序（同时保留原始下标），再用左右指针向中间扫描。排序 $O(n \log n)$ ，扫描 $O(n)$ ，总时间复杂度 $O(n \log n)$ 。

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
45/**
 * 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-07-28 18:13
 * update_at: 2026-07-28 18:15
 */
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 10005;

int n, target;
int nums[MAXN];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> target;
    for (int i = 0; i < n; i++) {
        cin >> nums[i];
    }

    vector<pair<int, int>> a(n);
    for (int i = 0; i < n; i++) {
        a[i] = {nums[i], i};
    }
    sort(a.begin(), a.end());

    int l = 0, r = n - 1;
    while (l < r) {
        int sum = a[l].first + a[r].first;
        if (sum == target) {
            cout << a[l].second << ' ' << a[r].second << '\n';
            return 0;
        }
        if (sum < target)
            l++;
        else
            r--;
    }

    return 0;
}

复杂度

时间复杂度：平均 $O(n)$ ，每个元素只扫描一次，每次字典查询和插入平均为 $O(1)$ 。
空间复杂度： $O(n)$ ，最坏情况下字典保存前面所有元素。

总结

当题目要求寻找满足关系的一对元素时，可以把“枚举另一个元素”改成“查询另一个元素”。本题把补数作为查询键，用额外的哈希表空间将二重枚举优化为一次扫描。

目录

题意

思路

代码

复杂度

总结