1. Two Sum

题目

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice. You can return the answer in any order.

Example 1:

1
2
3
Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

Example 2:

1
2
Input: nums = [3,2,4], target = 6
Output: [1,2]

Example 3:

1
2
Input: nums = [3,3], target = 6
Output: [0,1]

题目大意

在数组中找到两个数，使它们的和等于给定的目标值 target，返回这两个数的下标。每个输入保证有且仅有一个解，同一个元素不能使用两次。

你选用何种方法解题？

本题的核心是快速查找补数。对于每个元素 nums[i]，我们需要知道 target - nums[i] 是否已经在之前遍历过的元素中出现过——以及它出现的下标是什么。

方法一：哈希表（推荐）

遍历数组时，用哈希表（Python 字典）存储 值 → 下标 的映射。对于当前元素，计算其补数，如果补数已在哈希表中，直接返回两个下标。这是最优解：一次遍历，O(1) 的查找开销。

方法二：暴力枚举

双重循环遍历所有数对 (i, j)，检查和是否为 target。虽然直观，但 O(n²) 的时间复杂度在处理大规模数据时不可接受。仅作为对比列出。

解题过程

问题分析

输入：一个整数数组 nums 和一个目标整数 target。
输出：两个下标 [i, j]，满足 nums[i] + nums[j] == target 且 i ≠ j。

关键约束：每个输入有且仅有一个解。这意味着我们不需要处理无解或多解的情况，找到即可返回。

核心洞察

暴力做法之所以慢，是因为对于每个元素，我们都要重新扫描整个数组来寻找它的补数。如果我们能记住已经见过的元素及其位置，补数查找就变成了 O(1) 的哈希表查询。

算法流程

以 nums = [2, 7, 11, 15], target = 9 为例：

步骤 i nums[i] 补数 哈希表（seen） 操作
1 0 2 7 {} 7 不在表中，存入 {2: 0}
2 1 7 2 {2: 0} 2 在表中！返回 [0, 1]

这些方法具体怎么运用？

方法一：哈希表

数据结构：一个字典 seen，键是数组元素的值，值是该元素的下标。

核心逻辑：

  1. 遍历数组，用 enumerate 同时获取下标 i 和值 num
  2. 计算补数 need = target - num
  3. 若 need 已在 seen 中 → 找到答案，返回 [seen[need], i]
  4. 否则 → 将 {num: i} 存入 seen，继续遍历

为什么不会重复使用同一元素？ 因为我们是先查哈希表、后存入当前元素。查询时当前元素尚未入表，所以查到的补数一定是之前遍历过的不同元素。

边界情况：

  • nums = [3, 3], target = 6：第一个 3 存入 {3: 0}，第二个 3 的补数也是 3，在表中找到了下标 0，正确返回 [0, 1]。
  • 题目保证有解，因此遍历结束时必然已经返回，不需要额外的未找到处理。

方法二：暴力枚举

核心逻辑：

  1. 外层循环 i 从 0 到 n-1
  2. 内层循环 j 从 i+1 到 n-1（避免重复和顺序重复）
  3. 若 nums[i] + nums[j] == target → 返回 [i, j]

为什么 j 从 i+1 开始？ 避免 (i, i) 使用同一元素，也避免返回 (i, j) 和 (j, i) 两种排列。

复杂度

方法 时间复杂度 空间复杂度
哈希表 O(n) — 单次遍历，每次查找 O(1) O(n) — 最坏情况存储全部 n 个元素
暴力枚举 O(n²) — 双重循环遍历所有数对 O(1) — 仅使用常数个变量

总结与最佳选择

最快算法：哈希表（O(n)），比暴力枚举（O(n²)）快一个数量级。实际运行中，n = 10⁴ 时哈希表约 0.1ms，暴力枚举约 100ms。

工程最优选择：哈希表。虽然需要 O(n) 额外空间，但以空间换时间是工程中的标准权衡——现代内存充足，而 O(n²) 在大数据量下完全不可用。哈希表代码简洁、逻辑清晰，是这道题在面试和实际开发中的唯一推荐解法。暴力枚举仅在教学对比时有价值。

Code

方法一：哈希表（推荐）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
from typing import List

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        """
        哈希表法：一次遍历，边查边存。
        对于每个元素，先查补数是否已出现，再将自己存入哈希表。
        """
        seen: dict[int, int] = {}  # 值 → 下标

        for i, num in enumerate(nums):
            need = target - num
            if need in seen:
                return [seen[need], i]
            seen[num] = i

        return []  # 题目保证有解，此行不会执行

方法二：暴力枚举（不推荐，仅供对比）

1
2
3
4
5
6
7
8
9
10
11
from typing import List

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        """暴力枚举：O(n²) 时间，O(1) 空间。"""
        n = len(nums)
        for i in range(n):
            for j in range(i + 1, n):
                if nums[i] + nums[j] == target:
                    return [i, j]
        return []