给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/two-sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
解法一 暴力法
两层循环遍历所有可能的组合，当两数和等于target时返回
时间复杂度
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
for i in range(len(nums) - 1):
for j in range(i+1, len(nums)):
if target == (nums[i] + nums[j]):
return [i, j]
解法二 Hash法
遍历每个元素，用字典保存target减当前元素的结果和当前索引
- 如果 字典 内存在与当前元素值相等的key 时，返回key对应的value及当前索引
- 否则，将 (target - value): 索引 作为 键: 值对 存入字典
典型的空间换时间的算法
遍历一次即可，每一次循环的操作时间复杂度是，因此总的时间复杂度是
，空间复杂度是
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
_dict = {}
for i, num in enumerate(nums):
if num in _dict.keys():
return [_dict[num], i]
else:
_dict[target - num] = i
