| 题目名字 | 两数之和 |
|---|---|
| 链接 | https://leetcode-cn.com/problems/two-sum/ |
| 难度 | 简单 |
| 类型 | 数组 |
| 方法 | 暴力枚举、哈希表 |
注：题目中数组中同一个元素不能使用两遍。意思是：结果不能用两遍同一个数，并且假设只有一个结果。
python 实现
方法一：暴力枚举
1. 个人解决的代码
思路： 寻找两数之和，最简单的想法就是循环遍历，使用两层循环，从左到右，当我们使用遍历整个数组的方式寻找 target - x 时，需要注意到每一个位于 x 之前的元素都已经和 x 匹配过，因此不需要再进行匹配。而每一个元素不能被使用两次，所以我们只需要在 x 后面的元素中寻找 target - x。
# 为了增强代码的可读性，python3.5 之后，引入了一个 typing 模块，用来解释变量的类型。可有可无。
from typing import List
class Solution:
def twoSum(self, nums:List[int], target: int) -> List[int]:
id = 0
for i, x in enumerate(nums):
id += 1
for j, y in enumerate(nums[i+1:]):
if x + y == target:
return [i, j+id]
代码解读： 使用了 内置函数 enumerate() 获得 index， nums[i+1:] 使用 list 切片只考虑当前元素 后面的元素。
2. 官方实现：
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
n = len(nums)
for i in range(n):
for j in range(i + 1, n):
if nums[i] + nums[j] == target:
return [i, j]
代码解读： 官方的实现更加简洁。先获取了 nums 的 长度，然后使用 range 来仅仅遍历 index，思路和上面的类似。
3. 复杂度分析：
时间复杂度：\(O(N^2)\) , 其中 N 是数组中的元素数量。最坏情况下数组中任意两个数都要被匹配一次。
空间复杂度：\(O(1)\)
空间复杂度：如果程序所占用的存储空间和输入值无关，则该程序的空间复杂度就为 O(1)；反之，如果有关，则需要进一步判断它们之间的关系：
- 如果随着输入值 n 的增大，程序申请的临时空间成线性增长，则程序的空间复杂度用 O(n) 表示;
- 如果随着输入值 n 的增大，程序申请的临时空间成 n2 关系增长，则程序的空间复杂度用 O(n2) 表示；
- 如果随着输入值 n 的增大，程序申请的临时空间成 n3 关系增长，则程序的空间复杂度用 O(n3) 表示；
方法二：哈希表
思路： 注意到 方法一 的 时间复杂度 较高的原因是 寻找 target - x 的时间复杂度过高。
使用哈希表，可以将寻找 target - x 的时间复杂度降低到从 \(O(N)\) 降低到 \(O(1)\)。
这样我们创建一个哈希表，对于每一个 x，我们首先查询哈希表中是否存在 target - x，然后将 x 插入到哈希表中，即可保证不会让 x 和自己匹配。
class Solution:
def twoSum(self, nums:List[int], target:int) -> List[int]:
hashtable = dict()
for i, num in enumerate(nums):
if target - num in hashtable:
return [hashtable[target - num], i]
hashtable[num] = i
代码解读： Python 字典的底层实现是哈希表。当然字典也可以使用别的方式实现。实现字典的另一种常见方法是 red-black trees。每种方法都有各自的优缺点。红黑树总是可以在O（log n）中执行查找。哈希表可以在o（1）时间内执行查找，尽管根据输入，它可以降级为o（n）。
显然，这里的 key 是 nums 中的元素，而 value 是 对应的 index。
复杂度分析：
时间复杂度：\(O(N)\)，其中 N 是数组中的元素数量。对于每一个元素 x，我们可以 \(O(1)\) 地寻找 target - x。
空间复杂度：\(O(N)\)，其中 N 是数组中的元素数量。主要为哈希表的开销。
显然， 哈希表是 空间换时间。