题目：
leetcode1题目描述
解法：
1. 暴力解法
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
for i in range(len(nums)):
for j in range(i+1,len(nums)):
if nums[i] + nums[j] == target:
return [i, j]
这是最最容易想到的方法了......先用遍历一遍
中的每一个元素，然后再看
元素与后面的
元素之和是否等于
。
复杂度分析：
- 时间复杂度：
- 空间复杂度：
效率:
暴力解法效率
2. 哈希表法
暴力解法比较慢是因为我们用了两层循环，为了提高效率，我们可以选择“空间换时间”的方法，来降低第二层循环的时间。所以我们选择使用哈希表来降低查找时间。
2.1 两遍哈希
我们可以先遍历一遍，构建哈希表，其中元素的值作为key、元素的索引作为value，从而通过哈希表来确定元素在
中的索引位置。然后，再次遍历
，通过刚刚构建的哈希表确定是否有元素等于
。
需要注意的是，题目中说每个数只能用一次，所以一定要在if语句中加上条件i!=hashdict[diff]
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
hashdict = {num: index for index, num in enumerate(nums)}
# print(hashdict)
for i, num in enumerate(nums):
diff = target - nums[i]
if diff in hashdict and i!=hashdict[diff]: ##确保选中的是两个不同索引的数
return [i,hashdict[diff]]
复杂度分析：
- 时间复杂度：
- 空间复杂度：
：哈希表里存放了n个元素
效率:
可以看到，运行时间显著地降低了，从6.3s降低为0.06s。
两遍哈希效率
2.2 一遍哈希
2.1的方法中，哈希表的构建和查找是分开的，我们可以边构建边查找，从而进一步地降低运行时间。
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
hashdict = {}
for i, num in enumerate(nums):
diff = target - nums[i]
if diff in hashdict and i!=hashdict[diff]:
return[i, hashdict[diff]]
hashdict[num] = i
复杂度分析：
- 时间复杂度：
- 空间复杂度：
效率：
执行时间从0.060s降低到了0.048s。
一遍哈希效率
