哈希算法题目：两数之和

题目描述
给定一个整数数组 nums 和一个整数目标值 target，请在数组中找出和为目标值 target 的那两个整数，并返回它们的数组下标。假设每种输入只会对应一个答案，且同个元素不能使用两次。可以按任意顺序返回答案。

示例
输入：nums = [2, 7, 11, 15], target = 9
输出：[0, 1]
解释：nums[0] + nums[1] = 2 + 7 = 9，因此返回下标 [0, 1]。

解题思路

1. 暴力法（基础思路）

   • 遍历每个元素 nums[i]，再遍历其后的每个元素 nums[j]，检查是否满足 nums[i] + nums[j] == target。
   • 时间复杂度：O(n²)，效率较低。

2. 哈希表优化

   • 核心思想：用哈希表存储已遍历过的数字及其下标，将查找时间降至 O(1)。
   • 遍历数组时，计算当前数字与目标的差值 diff = target - nums[i]，若 diff 在哈希表中存在，则直接返回结果。

逐步推导
假设 nums = [2, 7, 11, 15], target = 9：

1. 初始化空哈希表 map，键为数字，值为下标。
2. 遍历第 1 个元素 i=0，nums[0]=2：
   • 计算差值 diff = 9 - 2 = 7。
   • 检查哈希表：7 不在表中，将 (2, 0) 存入哈希表。
3. 遍历第 2 个元素 i=1，nums[1]=7：
   • 计算差值 diff = 9 - 7 = 2。
   • 检查哈希表：2 存在于表中，对应下标 0。
   • 返回结果 [0, 1]。

代码实现（伪代码）

def twoSum(nums, target):
    map = {}  # 哈希表：数字 -> 下标
    for i, num in enumerate(nums):
        diff = target - num
        if diff in map:  # 检查差值是否已存在
            return [map[diff], i]  # 返回匹配的下标
        map[num] = i  # 将当前数字存入哈希表
    return []  # 无解情况（题目保证有解，可省略）

关键点

• 哈希表将查找时间优化至 O(1)，整体时间复杂度降至 O(n)。
• 仅需遍历数组一次，空间复杂度为 O(n)（存储哈希表）。
• 避免重复使用同一元素：因为先检查后存入，当前元素不会与自己匹配。