1-两数之和
万里长征始于足下。
给定一个整数数组 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
解法 1：双重循环
乍一看，挺简单，不就两重循环么。说干就干。
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
length = len(nums)
ret = []
isFind=False
for i in range(length):
for j in range(length):
if i==j:
continue
elif nums[i] + nums[j] == target:
isFind=True
ret.append(i)
ret.append(j)
if isFind:
return ret
return ret
这里再提供一个计算函数执行时间的装饰器（学以致用）
def print_func_time(function):
@wraps(function)
def func_time(*args, **kwargs):
t0 = time.perf_counter()
result = function(*args, **kwargs)
t1 = time.perf_counter()
print("Total running time: %s s" % (str(t1 - t0)))
return result
return func_time
当然，事情没有那么简单，显然而且必然的，在最后一组数据下超时了。
此处数据过长，就不贴了，自己去超时的地方看看就ok了
自己本地跑也是要 11-12s 左右的（视电脑不同而不同。）
Total running time: 12.628380413 s
[8010, 8011]
暂时没有什么错误发生，那么接下来就是考虑优化的事情了。
-
首先就是我们的 ret 不必要存在，可以直接返回的时候封装成
list就可以了，可以省掉一点 append 操作的时间。 -
然后就是我们的 isFind 判断是不必要的，题目中已经假设了必然有且只有一个结果，我们发现结果的时候直接返回就可以了。
-
再接着，我们的
j不必要从头开始遍历，会造成冗余的循环。只要从i+1的地方开始就可以了。
修改后的代码长这样：
def twoSum(self, nums: List[int], target: int) -> List[int]:
length = len(nums)
for i in range(length):
for j in range(i+1,length):
if nums[i] + nums[j] == target:
return [i,j]
return []
时间下降了很多：
Total running time: 6.893857144 s
[8010, 8011]
当然，这显然不符合我们的要求，虽然题目不说，但是，我们肯定要压缩到 1s 以内的。
考虑到，普通 index 的遍历速度 < enumerate <iterator。
但是我们这边需要我们遍历的索引。所以我们考虑使用 enumerate 而不是使用 iterator。
Python 中加法操作好像比较耗时，在大量操作后，iterator 的操作时间已经比 enumerate 直接取索引高很多了。
所以不考虑使用 iterator，在迭代内部计算索引。（实操证明过了，不信可以自己实验）
时间再次下降 1 秒：
def twoSum(self, nums: List[int], target: int) -> List[int]:
length = len(nums)
# newNums = sorted(enumerate(nums),key=lambda x:x[1])
for i,item in enumerate(nums):
for j in range(i+1,length):
if item+nums[j] == target:
return [i,j]
Total running time: 5.895048940000001 s
[8010, 8011]
这时候我们再考虑，target值是两者相加得到（数据组中有负数存在需要考虑）。
target>=0的情况下，必然有一个数是小于target的target<0的情况下，必然有一个数是大于target的
那么，我们可以先对数组进行一下排序，以对循环进行剪枝：
def twoSum(self, nums: List[int], target: int) -> List[int]:
length = len(nums)
newNums = sorted(enumerate(nums),key=lambda x:x[1])
if target >= 0:
for i in range(length):
if i > target:
break
for j in range(i + 1, length):
if newNums[i][1] + newNums[j][1] == target:
return [newNums[i][0], newNums[j][0]]
return []
elif target < 0:
for i in range(length):
if i < target:
break
for j in range(i + 1, length):
if newNums[i][1] + newNums[j][1] == target:
return [newNums[i][0], newNums[j][0]]
return []
我们发现已经低于 0.01 秒了。已经能通过 LeetCode 的提交了。但是你还是 Too young too simple。
那是因为我们的数据有点特殊，我们在此把target替换成（25196+25194）= 50390
我们发现，时间还是超时了（当然是本地跑的，10s 左右）
Total running time: 10.42657594 s
[12597, 12598]
当然不能因为特殊而特殊啦
本着科学研究的精神，我们进行一下升华
解法 2：哈希表
我们反过来考虑一下，我们何苦去它有的里面找有两个数相加得到目标值呢。凭啥听他的一定要到它里面找。
（当然得从里面找）
但是，我们可以考虑一下，我从list中取第i个值，然后计算出target-list[i]，然后我去 list 里面找，我计算出来的这个差值是否在 list
中，如果在，那就对了，如果不在，就取i+1进行下一步运算。
当然不能用双重循环啦，那跟第一种方法没区别了。
我们考虑到哈希表，Python 中内置的字典dict就是一个哈希表：
def twoSum(self, nums: List[int], target: int) -> List[int]:
hashmap = {}
for index, num in enumerate(nums):
another_num = target - num
if another_num in hashmap:
return [hashmap[another_num], index]
hashmap[num] = index
return None
同时我们边存边判断，这样可以减少一次循环。
你可能考虑到，哈希表，不存在重复值，但是我的数组可能存在重复值，会不会有影响。
看代码：
- 我们外层循环是对
enumerate(nums)进行循环的，所以每一个原有的值都会遍历到 - 题目中有说到有且只有一个答案。那么，重复值引起的有两种选择的情况也是不存在的。