letcode[001] 两数之和

题目001
题目地址：两数之和

1. 主要考虑题目中的诸多异常情况，例如相加的两个数相等等情况，需要进行规避。
2. 思路三看起来是最佳的，但初学者可能难以想到。

思路1：自拟思路——差值匹配

对每个数据，获取目标值与该数据的差，再匹配剩余的数据，找到相等的第一个数据即为正确数据
总结：较为冗余，会存在重复相加的问题
用时：2656 ms

def twoSum1(nums, target):
    for i in nums:
        p1=nums.index(i)
        nums_bak=nums.copy()
        j=target-i
        del nums_bak[p1]
        if j in nums_bak:
            p2=nums_bak.index(j)+1
            return [p1,p2]

思路2：官方暴力思路

对第i位的数据和i之后的数据相加，如果相加后的和与target相等，即返回目标值
总结： 测试结果居然比上一个慢。。。
用时：5816 ms

def twoSum2(nums, target):
    nums_length=len(nums)
    for i in range(nums_length):
        j=i+1
        for j in range(j,nums_length):
            if nums[i]+nums[j]==target:
                return [i,j]

思路3：网友思路——字典

使用enumerate将列表组合为索引序列，遍历序列，并和特定字典里面的数据匹配，如果序列某个值和字典里的值相加正好为target，则返回结果；否则将该序列值添加进字典
总结：字典比列表更快速（空间换时间）
用时：1552 ms

def twoSum3(nums, target):
    d={}
    for i,item in enumerate(nums):
        temp=target-item
        for key,value in d.items():
            if value==temp:
                return [key,i]
        d[i]=item

#另一种leetcode中最快的思路（少用一次for循环可以提升效率）：
def twoSum5(nums, target):
    dict = {}
    for i, x in enumerate(nums):
        a = target - x
        if a not in dict:
            dict[x] = i
        else:
            return [dict[a], i]

思路4：自拟思路——思路1的优化

解决不用匹配第i个数据之前的数据
总结:相比思路一确实有一定的改进
用时：1768 ms

def twoSum4(nums, target):
    for i in nums:
        p1=nums.index(i)
        nums_bak=nums[p1+1:]
        j=target-i
        if j in nums_bak:
            p2=nums_bak.index(j)+p1+1
            return [p1,p2]