从两数之和到哈希表优化：探索高效算法实现

<｜begin▁of▁sentence｜># 1. 两数之和 ## 题目 给定一个整数数组 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 <= nums.length <= 104 -109 <= nums[i] <= 109 -109 <= target <= 109 只会存在一个有效答案 ## 进阶 你可以想出一个时间复杂度小于 O(n2) 的算法吗？ ## 解题思路 最直接的方法是使用双重循环遍历数组中的每一对数字，检查它们的和是否等于目标值。这种方法的时间复杂度是O(n^2)，其中n是数组的长度。 为了优化，我们可以使用哈希表（在Python中是字典）来存储每个数字的索引。这样，我们可以通过一次遍历数组，对于每个元素，检查目标值减去当前元素的差值是否已经在哈希表中。如果在，我们就找到了两个数字，它们的和等于目标值。这种方法的时间复杂度是O(n)，因为我们只需要遍历数组一次，而哈希表的查找操作是O(1)的。 具体步骤： 1. 初始化一个空的字典来存储数字和它们的索引。 2. 遍历数组，对于每个数字，计算目标值减去当前数字的差值。 3. 检查这个差值是否已经在字典中。如果是，返回差值的索引和当前索引。 4. 如果不是，将当前数字和它的索引添加到字典中。 这种方法确保了我们不会使用同一个元素两次，因为我们在检查差值时，当前元素还没有被添加到字典中。 ## 代码 ```python def twoSum(nums, target): num_map = {} for i, num in enumerate(nums): complement = target - num if complement in num_map: return [num_map[complement], i] num_map[num] = i return [] ``` ## 相关主题 - 数组 - 哈希表 ## 相似题目 - 三数之和 (中等) - 四数之和 (中等) - 两数之和 II - 输入有序数组 (中等) - 两数之和 III - 数据结构设计 (简单) - 两数之和 IV - 输入 BST (简单) - 小于 K 的两数之和 (简单)