好的，我们这次来详细讲解 LeetCode 第 1 题：两数之和（Two Sum）。

1. 题目描述

题目链接：
https://leetcode.com/problems/two-sum/

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

你可以假设每种输入只会对应一个答案，并且你不能重复利用这个数组中同样的元素。
你可以按任意顺序返回答案。

示例 1：

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

示例 2：

输入：nums = [3,2,4], target = 6
输出：[1,2]

示例 3：

输入：nums = [3,3], target = 6
输出：[0,1]

约束条件：

• 数组长度在 2 到 10^4 之间
• 数值范围在 -10^9 到 10^9 之间
• target 也在 -10^9 到 10^9 之间
• 只会有一个有效答案

2. 思路分析

2.1 最直观的解法：暴力枚举

我们可以用两个循环，第一个循环枚举第一个数 nums[i]，第二个循环枚举第二个数 nums[j]（j > i），检查 nums[i] + nums[j] == target 是否成立。

• 时间复杂度：O(n²)
• 空间复杂度：O(1)

这种方法简单，但在数据量较大时（n 最大 10^4）会超时。

2.2 优化思路：使用哈希表

我们希望快速查找 target - nums[i] 是否在数组中出现过，并且知道它的下标。
哈希表（字典） 可以实现 O(1) 时间复杂度的查找。

步骤：

1. 创建一个哈希表 map，用来存储 数值 -> 下标 的映射。

2. 遍历数组 nums，对于当前元素 nums[i]：

   • 计算 complement = target - nums[i]
   • 检查 complement 是否在 map 中：
     • 如果在，说明找到了，返回 [map[complement], i]
     • 如果不在，将 nums[i] 和下标 i 存入 map

3. 如果遍历结束没找到，返回空数组（题目保证有解，所以不会执行到这一步）。

为什么先查再存？
因为如果先存再查，可能会重复使用同一个元素（比如 target = 6, nums[i] = 3，先存 3 再查 3，会找到自己，不符合“不能重复利用同一个元素”的要求）。
先查再存可以避免这种情况。

3. 详细推导与示例

示例 1：nums = [2,7,11,15], target = 9

初始化：map = {}

• i = 0, nums[0] = 2
  complement = 9 - 2 = 7
  map 中没有 7 → 存入 map: {2:0}

• i = 1, nums[1] = 7
  complement = 9 - 7 = 2
  map 中有 2，下标是 0 → 找到答案 [0, 1]

示例 3：nums = [3,3], target = 6

初始化：map = {}

• i = 0, nums[0] = 3
  complement = 6 - 3 = 3
  map 中没有 3 → 存入 map: {3:0}

• i = 1, nums[1] = 3
  complement = 6 - 3 = 3
  map 中有 3，下标是 0 → 找到答案 [0, 1]

4. 代码实现（Python）

def twoSum(nums, target):
    hashmap = {}
    for i, num in enumerate(nums):
        complement = target - num
        if complement in hashmap:
            return [hashmap[complement], i]
        hashmap[num] = i
    return []  # 题目保证有解，实际不会执行到这里

复杂度分析：

• 时间复杂度：O(n)，只需遍历一次数组，哈希表操作平均 O(1)
• 空间复杂度：O(n)，最坏情况下需要存储 n 个元素的映射

5. 关键点总结

1. 为什么用哈希表：将查找时间从 O(n) 降到 O(1)，从而总体时间复杂度从 O(n²) 降到 O(n)。
2. 先查后存：避免同一个元素被使用两次。
3. 处理重复元素：当有重复数字时，比如 [3,3]，因为我们在找到答案之前只存了第一个 3 的下标，遇到第二个 3 时查到的 complement=3 是第一个 3 的下标，不会冲突。
4. 只遍历一次：可以在一次遍历中完成查找和存储，不需要先建立完整哈希表再查找。

6. 扩展思考

• 如果数组是有序的，可以用双指针法在 O(n) 时间、O(1) 空间内解决（但本题无序，排序会丢失下标信息，除非记录原下标，那样空间还是 O(n)）。
• 如果要求返回所有不重复的数对（而不是下标），可以用另一种双指针或哈希法。
• 如果数组很大，无法一次性加载到内存，可以考虑外部哈希或分治策略（但本题 n ≤ 10^4，一般内存可容纳）。

这样一步步分析，你应该能清晰地理解「两数之和」的解法原理和优化过程了。