算法路飞：
视频: https://www.bilibili.com/video/BV1Tnd2BDEBp
代码: https://github.com/jusway/Leetcode_learn
https://leetcode.cn/problems/two-sum/
- 两数之和 简单
给定一个整数数组 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) 的算法吗？
暴力破解的思路最直接，用两层循环枚举数组中的两个数。外层固定第一个数，内层从它后面的元素开始找第二个数，如果两数之和等于 target，就返回它们的下标。这种写法很好理解，但需要比较每一对组合，时间复杂度是 O(n²)。
1from typing import List
2class Solution1:
3 # 暴力破解
4 def twoSum(self, nums: List[int], target: int) -> List[int]:
5 for i,item in enumerate(nums):
6 for j in range(i+1,len(nums)):
7 post=nums[j]
8 if item+post==target:
9 return [i,j]
第二种写法使用哈希表，也就是 Python 里的字典。先遍历一遍数组，把每个数字和它对应的下标存进字典里。然后再遍历数组，计算当前数字还需要的另一个数 other = target - item，如果 other 在字典中，并且不是当前元素本身，就返回两个下标。这样查找另一个数的过程可以用哈希表快速完成。
1class Solution2:
2 # 利用哈希表
3 def twoSum(self, nums: List[int], target: int) -> List[int]:
4 cache={}
5 for i,item in enumerate(nums):
6 cache[item]=i
7
8 for i,item in enumerate(nums):
9 other=target-item
10 if other in cache and cache[other]!=i:
11 return [i,cache[other]]
第三种写法是在遍历的过程中一边查找一边存入哈希表。每次遍历到一个数字时，先计算它需要的另一个数 other，如果 other 已经在哈希表中，说明前面已经出现过可以和当前数字组成答案的元素，直接返回两个下标；如果没找到，就把当前数字和下标加入哈希表。这样只需要遍历一次数组，时间复杂度是 O(n)。
1class Solution:
2 # 哈希表进一步
3 def twoSum(self, nums: List[int], target: int) -> List[int]:
4 cache={}
5 for i,item in enumerate(nums):
6 other=target-item
7 if other in cache:
8 return [i,cache[other]]
9 cache[item]=i