leetcode_001两数之和

**两数之和**

给定一个整数数组 `nums` 和一个目标整数 `target`，找出两个数字的下标，使得它们加起来等于 `target`。你可以假设每个输入只有一种解。

示例：

* 输入：`nums = [2,7,11,15]`, `target =9`
输出：`[0,1]`

**解决方案**

我们将使用哈希表来存储数字及其下标。具体来说，我们将在哈希表中存储每个数字的值和其下标。

class Solution:
 def twoSum(self, nums: List[int], target: int) -> List[int]:
 # 创建一个空哈希表 num_dict = {}
 # 遍历数组中的每个数字 for i in range(len(nums)):
 # 计算当前数字与目标值之间的差值 diff = target - nums[i]
 # 如果该差值在哈希表中存在，则返回下标 if diff in num_dict:
 return [num_dict[diff], i]
 # 否则，将当前数字及其下标添加到哈希表中 num_dict[nums[i]] = i # 如果没有找到解决方案，则返回空列表 return []

**注释**

* 我们首先创建一个空哈希表 `num_dict` 来存储数字及其下标。
* 然后，我们遍历数组中的每个数字，并计算当前数字与目标值之间的差值 `diff`。
* 如果该差值在哈希表中存在，则返回下标，因为我们找到了两个数字，它们加起来等于 `target`。
* 否则，我们将当前数字及其下标添加到哈希表中，以便在后续遍历时可以检查是否找到解决方案。
* 如果没有找到解决方案，则返回空列表。

**时间复杂度**

该算法的时间复杂度为 O(n)，其中 n 是数组中的元素数量。我们只需要遍历一次数组，因此时间复杂度是线性的。

**空间复杂度**

该算法的空间复杂度为 O(n)。我们使用一个哈希表来存储数字及其下标，大小与输入数组相同。

**总结**

两数之和问题可以使用哈希表解决。我们首先创建一个空哈希表，然后遍历数组中的每个数字，并计算当前数字与目标值之间的差值。如果该差值在哈希表中存在，则返回下标。否则，我们将当前数字及其下标添加到哈希表中，以便在后续遍历时可以检查是否找到解决方案。