难度: 简单
给定一个整数数组 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) 的算法吗？
运行时间: 28 ms
内存: 16.1 MB
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
memo = dict()
for i, num in enumerate(nums):
if target - num in memo:
return [i, memo[target-num]]
memo[num] = i
这个题解使用了哈希表来存储数组中每个元素的值和对应的下标。遍历数组的过程中，对于当前元素 num，先判断 target - num 是否在哈希表中，如果存在，则说明找到了两个数的和为 target 的情况，直接返回这两个数的下标。如果不存在，则将当前元素 num 和其下标存入哈希表中。这样可以在遍历的过程中快速判断是否存在与当前元素匹配的另一个数。
时间复杂度: O(n)
空间复杂度: O(n)
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
# 创建一个哈希表用于存储数组元素和下标
memo = dict()
# 遍历数组
for i, num in enumerate(nums):
# 判断 target - num 是否在哈希表中
if target - num in memo:
# 如果存在，返回两个数的下标
return [i, memo[target-num]]
# 如果不存在，将当前元素和下标存入哈希表
memo[num] = i
为什么在遍历数组的同时更新哈希表，而不是先构建完整的哈希表再进行查找？
这种方法允许在单次遍历中同时进行查找和更新操作，从而将算法的时间复杂度控制在O(n)。如果我们先构建完整的哈希表，再进行查找，可能会导致对每个元素重复查找，增加不必要的操作和时间消耗。此外，同时更新哈希表可以保证我们在找到第一个符合条件的组合后立即停止遍历，提高效率。
在判断`target - num`是否在哈希表中时，为什么可以保证不会重复使用同一个元素？
在遍历的过程中，每遇到一个元素就立即检查其配对元素（target - num）是否已存在于哈希表中。由于我们是在将元素num添加到哈希表之前进行检查的，因此哈希表中存储的都是之前遍历过的元素。这样一来，我们找到的配对元素必然是不同的元素，避免了使用同一个元素两次。
如果数组中存在多对数字的和等于`target`，这个算法是否能找到所有这些组合？
这个算法只能找到第一对符合条件的两个数字。一旦找到一对符合条件的数字，算法就会结束并返回这对数字的下标。因此，它不会继续寻找其他可能的组合。如果需要找到所有符合条件的组合，需要对算法进行修改，使其能够继续遍历整个数组，收集所有有效的数字对。
这种方法对数组的顺序有没有特殊要求？
这种方法不对数组的顺序有特殊要求。无论数组中的元素如何排序，算法都能通过哈希表有效地查找到目标元素。数组的不同排列只影响找到的那对数字的顺序，但不影响算法的功能性。
在实际应用中，如何处理哈希表的冲突？
在哈希表中，冲突是指两个不同的键因为哈希函数的映射结果相同而被分配到同一个位置。处理方法通常包括链地址法（使用链表处理冲突）、开放地址法（寻找空白的哈希表位置）、双重哈希法（使用第二个哈希函数）等。在本算法中，由于键是数组中的元素值，若元素值相同，则更新其索引，这在处理具体问题时通常不会导致问题，因为我们只关心能否找到和为target的两个不同数字。