在算法学习的道路上，“两数之和” 是绕不开的经典入门问题。它不仅是 LeetCode 的第一道题目，更是理解 “时间复杂度优化”“哈希表应用” 等核心思想的绝佳案例。本文将从问题定义出发，逐步拆解暴力解法的局限，深入讲解哈希表优化思路，并拓展多场景下的变种问题，帮助你彻底掌握这一基础算法的本质。
一、问题定义：明确需求是解题的第一步
首先，我们需要清晰理解 “两数之和” 的核心需求。根据 LeetCode 官方定义，问题描述如下：
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案，并且你不能使用同一个元素两次。
你可以按任意顺序返回答案。
关键约束条件拆解
- 输入特性：数组元素为整数（可正可负），且保证有且仅有一个有效答案；
- 输出要求：返回两个元素的下标（而非元素值），顺序无关；
- 核心限制：不能重复使用同一元素（即同一个下标不能被选中两次）。
示例理解
以经典示例为例：
- 输入：nums = [2,7,11,15]，target = 9
- 输出：[0,1]（因 nums[0] + nums[1] = 2 + 7 = 9）
这个示例看似简单，但背后隐藏的解题思路差异，会直接影响算法的效率 —— 这也是我们接下来要重点讨论的内容。
二、暴力解法：直观但低效的 “穷举思维”
面对 “找两个数之和等于目标值” 的需求，最直观的思路是 “遍历所有可能的两数组合”，这就是暴力解法的核心思想。
算法思路
- 遍历数组中的每一个元素 nums[i]（i 从 0 到数组长度 - 2）；
- 对于每个 i，再遍历数组中 i 之后的元素 nums[j]（j 从 i+1 到数组长度 - 1）；
- 检查 nums[i] + nums[j] 是否等于 target，若等于则直接返回 [i, j]。
代码实现（Python）
pyt复制
def twoSum(nums: list[int], target: int) -> list[int]:
# 外层循环遍历第一个元素
for i in range(len(nums)):
# 内层循环遍历第二个元素（避免重复计算 i=j 的情况）
for j in range(i + 1, len(nums)):
if nums[i] + nums[j] == target:
return [i, j]
# 题目保证有解，此处仅为语法完整性
return []
算法特性分析
- 时间复杂度：O (n²)。外层循环执行 n 次，内层循环平均执行 n/2 次，整体为嵌套循环的乘积级复杂度。当数组长度 n 较大（如 10⁴ 以上）时，会出现明显的性能瓶颈。
- 空间复杂度：O (1)。仅使用了 i、j 两个循环变量，未额外占用与数组长度相关的存储空间。
暴力解法的优点是 “思路简单、代码易写”，但缺点也极其明显 —— 效率过低。在实际工程中，若处理大规模数据，这种解法几乎无法使用。因此，我们需要思考：如何通过 “空间换时间” 来优化时间复杂度？
三、哈希表优化：O (n) 时间复杂度的最优解
优化的核心思路是 “减少查找的时间成本”。暴力解法中，内层循环的本质是 “查找与 nums[i] 配对的 target - nums[i] 是否存在”，而哈希表（Python 中的 dict）的查找操作时间复杂度为 O (1)，恰好可以解决这一痛点。
算法思路（一次遍历版）
我们可以在遍历数组的同时，将 “元素值” 与 “下标” 存入哈希表，并实时检查当前元素所需的 “互补值”（target - 当前元素值）是否已在哈希表中：
- 初始化一个空的哈希表 hash_map，用于存储 “元素值 → 下标” 的映射；
- 遍历数组中的每个元素 nums[i]（i 从 0 开始）：
- 计算互补值 complement = target - nums[i]；
- 检查 complement 是否在 hash_map 中：
- 若存在，说明之前已遍历过 complement，直接返回 [hash_map[complement], i]；
- 若不存在，将当前元素 nums[i] 和其下标 i 存入 hash_map；
- 遍历结束前必然会找到答案（题目保证有解）。
代码实现（Python）
pyth复制
def twoSum(nums: list[int], target: int) -> list[int]:
hash_map = {} # 键：元素值，值：元素下标
for i in range(len(nums)):
complement = target - nums[i]
# 检查互补值是否已存在于哈希表中
if complement in hash_map:
return [hash_map[complement], i]
# 若不存在，将当前元素存入哈希表（注意顺序：先查后存，避免重复使用同一元素）
hash_map[nums[i]] = i
return []
