哈希算法题目：两数之和

题目描述

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

你可以假设每种输入只对应一个答案，并且 同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

示例：

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

限制条件：

• 数组长度在 \(2 \leq n \leq 10^4\) 范围内
• 数组元素和 target 均在 \(-10^9\) 到 \(10^9\) 之间
• 只会有一个有效答案

解题思路

这个问题本质上是要找出数组中两个数，它们的和等于目标值。最简单的想法是暴力枚举，即用两层循环遍历所有可能的数对。但这样时间复杂度是 \(O(n^2)\)，在数组很大时效率很低。
我们可以利用哈希表（在大多数编程语言中体现为字典或映射）来优化这个过程，将查找时间从 \(O(n)\) 降低到 \(O(1)\)，从而使整体时间复杂度降到 \(O(n)\)。

逐步解题过程

第1步：理解查找关系
假设当前正在看数组中的第 \(i\) 个数 nums[i]，我们需要找到另一个数 complement = target - nums[i]，使得两数之和为 target。
关键点在于，我们不需要在每遇到一个数时都回头去数组里搜索，而是可以在遍历过程中记录下已经遍历过的数及其下标，之后遇到新数时直接在记录中查找“互补数”是否存在。

第2步：选择数据结构
为了实现高效查找，我们选用哈希表（在 Python 中是 dict，在 Java 中是 HashMap，在 C++ 中是 unordered_map）。

• 键（key）：数组中某个数的值
• 值（value）：这个数在数组中的下标

这样，当我们需要查找一个数 complement 时，只需检查哈希表中是否有这个键，如果有，就能立即获取其下标。

第3步：算法步骤详解

1. 初始化一个空的哈希表 num_to_index。

2. 遍历数组 nums，对于每个下标 i 和对应的值 num = nums[i]：

   • 计算 complement = target - num。
   • 在哈希表中查找 complement：
     • 如果找到了，说明之前已经遍历过这个互补数，我们找到了答案，直接返回 [num_to_index[complement], i]。
     • 如果没有找到，将当前的数 num 及其下标 i 存入哈希表，继续遍历。

3. 由于题目保证一定有解，循环结束时一定会找到答案，无需额外处理无解情况。

第4步：例子推演

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

• 初始化哈希表：{}
• i = 0, num = 2：
  • complement = 9 - 2 = 7
  • 哈希表中没有 7
  • 存入 {2: 0}
• i = 1, num = 7：
  • complement = 9 - 7 = 2
  • 哈希表中有 2，对应下标 0
  • 找到答案，返回 [0, 1]

第5步：为什么这个算法正确？

因为我们顺序遍历数组，对于每个数，我们查找的互补数只可能在它之前出现过（否则就是它之后出现的数与当前数配对，但那样会在后续遍历中由另一个数来发现这个配对，因为遍历是顺序的）。
哈希表的查找是常数时间，所以整个算法只需要一次遍历，时间复杂度是 \(O(n)\)。
空间复杂度是 \(O(n)\)，因为哈希表最多存储 n 个元素。

第6步：边界情况

• 如果数组中有重复元素，比如 nums = [3, 3], target = 6，算法仍然有效，因为当遍历到第二个 3 时，哈希表中已经存了第一个 3 的下标，能立即找到互补数。
• 注意：题目要求同一个元素不能使用两次，但这里的“使用”是指在一次答案中不能下标重复。在 [3, 3] 例子中，我们返回的是两个不同下标 [0, 1]，是符合题意的。

第7步：代码示例（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 []  # 根据题目保证不会执行到这里

核心哈希思想总结

这个题目是哈希表的经典入门题，核心思想是 “空间换时间”：
通过额外的哈希表存储已遍历元素的信息，将原本需要两层循环的查找过程，转化为一次遍历 + 常数时间的查找，从而显著提升效率。
这是很多哈希相关算法的基础模式——当我们需要快速查找某个值是否出现过、出现的位置或次数时，哈希表往往是首选数据结构。