企业官网建设流程全解析

​在算法学习的道路上，“两数之和” 是绕不开的经典入门问题。它不仅是 LeetCode 的第一道题目，更是理解 “时间复杂度优化”“哈希表应用” 等核心思想的绝佳案例。本文将从问题定义出发，逐步拆解暴力解法的局限，深入讲解哈希表优化思路，并拓展多场景下的变种问题，帮助你彻底掌握这一基础算法的本质。​

一、问题定义：明确需求是解题的第一步​

首先，我们需要清晰理解 “两数之和” 的核心需求。根据 LeetCode 官方定义，问题描述如下：​

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

你可以假设每种输入只会对应一个答案，并且你不能使用同一个元素两次。​

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

​

关键约束条件拆解​

1. 输入特性：数组元素为整数（可正可负），且保证有且仅有一个有效答案；​

1. 输出要求：返回两个元素的下标（而非元素值），顺序无关；​

1. 核心限制：不能重复使用同一元素（即同一个下标不能被选中两次）。​

示例理解​

以经典示例为例：​

• 输入：nums = [2,7,11,15]，target = 9​

• 输出：[0,1]（因 nums[0] + nums[1] = 2 + 7 = 9）​

这个示例看似简单，但背后隐藏的解题思路差异，会直接影响算法的效率 —— 这也是我们接下来要重点讨论的内容。​

二、暴力解法：直观但低效的 “穷举思维”​

面对 “找两个数之和等于目标值” 的需求，最直观的思路是 “遍历所有可能的两数组合”，这就是暴力解法的核心思想。​

算法思路​

1. 遍历数组中的每一个元素 nums[i]（i 从 0 到数组长度 - 2）；​

1. 对于每个 i，再遍历数组中 i 之后的元素 nums[j]（j 从 i+1 到数组长度 - 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 - 当前元素值）是否已在哈希表中：​

1. 初始化一个空的哈希表 hash_map，用于存储 “元素值 → 下标” 的映射；​

1. 遍历数组中的每个元素 nums[i]（i 从 0 开始）：​

• 计算互补值 complement = target - nums[i]；​

• 检查 complement 是否在 hash_map 中：​

• 若存在，说明之前已遍历过 complement，直接返回 [hash_map[complement], i]；​

• 若不存在，将当前元素 nums[i] 和其下标 i 存入 hash_map；​

1. 遍历结束前必然会找到答案（题目保证有解）。​

代码实现（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 []​

​