两数之和

题目描述

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案，并且你不能使用同一个元素两次。你可以按任意顺序返回答案。

示例：

• 输入：nums = [2, 7, 11, 15], target = 9
• 输出：[0, 1]
• 解释：因为 nums[0] + nums[1] == 9，返回 [0, 1]。

解题过程

步骤 1：暴力解法（基础思路）

最直观的想法是：遍历数组中的每个元素 nums[i]，对于每个 i，再遍历其后的每个元素 nums[j]（j > i），检查两者之和是否等于 target。

• 时间复杂度：O(n²)，其中 n 是数组长度。
• 空间复杂度：O(1)。

代码示例（Python）：

def twoSum(nums, target):
    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 []

缺点： 当数组很大时，两层循环非常慢。

步骤 2：使用哈希表优化查找

我们观察到：对于每个 nums[i]，我们需要快速判断 target - nums[i] 是否在数组中已经出现过，并获取其下标。这正好是查找操作，哈希表（在 Python 中是字典）可以在 O(1) 时间内完成。

思路演进：

1. 创建一个空的哈希表 num_to_index，用于存储 数值 -> 下标 的映射。
2. 从左到右遍历数组：
   • 对于当前元素 nums[i]，计算 complement = target - nums[i]。
   • 检查 complement 是否在哈希表中：
     • 如果在，说明找到了两个数 complement 和 nums[i]，直接返回它们的下标 [num_to_index[complement], i]。
     • 如果不在，将当前数值 nums[i] 及其下标 i 存入哈希表。
3. 如果遍历结束没找到，返回空列表（根据题目假设，这种情况不会发生）。

为什么边遍历边存储？

• 这样可以确保我们不会重复使用同一个元素（因为当前元素是后来才加入哈希表的，查找时只能找到它之前的元素）。
• 同时，我们只需要遍历数组一次。

步骤 3：详细示例解析

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

1. 初始化：num_to_index = {}（空字典）。
2. i = 0：nums[0] = 2。
   • complement = 9 - 2 = 7。
   • 检查哈希表：7 不存在。
   • 存储：num_to_index[2] = 0。
3. i = 1：nums[1] = 7。
   • complement = 9 - 7 = 2。
   • 检查哈希表：2 存在，对应下标 0。
   • 找到答案：返回 [0, 1]。

遍历结束，得到结果。

步骤 4：代码实现（Python）

def twoSum(nums, target):
    num_to_index = {}  # 数值 -> 下标 的映射
    for i, num in enumerate(nums):
        complement = target - num
        if complement in num_to_index:
            return [num_to_index[complement], i]
        num_to_index[num] = i
    return []  # 根据题目假设，不会执行到这里

复杂度分析：

• 时间复杂度：O(n)。我们只遍历了一次数组，每次查找 complement 是 O(1) 操作。
• 空间复杂度：O(n)。最坏情况下，哈希表需要存储 n-1 个元素（例如答案在最后两个元素时）。

步骤 5：边界情况与注意事项

1. 有多个解？ 题目保证“只会对应一个答案”，所以找到一组即可停止。
2. 数组元素重复？ 例如 nums = [3, 3], target = 6。我们的算法依然有效：
   • i=0: 哈希表为空，存入 {3: 0}。
   • i=1: complement = 3，在哈希表中找到下标 0，返回 [0, 1]。
3. 负数或零？ 算法完全通用，因为哈希表存储的是数值本身，与正负无关。
4. 大数或溢出？ 在 Python 中整数无范围限制，无需担心。在其他语言中，一般题目会给定数值范围（如 32 位整数），通常不会溢出。

步骤 6：扩展思考

1. 如果数组已排序？ 可以使用双指针法（头尾指针向中间移动），时间复杂度 O(n)，空间复杂度 O(1)，但排序会改变下标，除非额外存储原下标。
2. 如果要求返回所有不重复的数对？ 需要更复杂的处理，可能涉及排序去重。
3. 哈希冲突的影响？ 在 Python 字典中，冲突由内部机制处理，平均仍为 O(1) 查找。自己实现哈希表时，需选择合适的冲突解决策略（如链地址法）。

总结

• 核心技巧：利用哈希表将“查找”时间从 O(n) 降为 O(1)，将整体时间复杂度从 O(n²) 优化到 O(n)。
• 适用场景：需要快速查找“互补值”的问题。
• 类似问题：三数之和、四数之和等，虽然更复杂，但“两数之和”的哈希思想是基础。

通过这个题目，我们不仅学会了一种高效解法，更重要的是掌握了 “以空间换时间” 和 “利用哈希表加速查找” 的经典算法思维。