leetcode练习1----两数之和

问题需求

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target  的那 两个 整数，并返回它们的数组下标。（同一个数组下标不能出现两次）

1.自己的思想：

        利用两个变量i，j分别去遍历数组，嵌套遍历，i从零开始，j从i+1到nums.length-1。然后去判断num[i]+num[j]==target,若相等，则return [i,j],不等则继续遍历。

        代码无法落地，实现不了；而且发现这好像是c语言的思想，与python不沾边；对python基础掌握的还是不够牢靠，于是参考了大神的代码

2.大神的思想：

用python中的list的相关函数求解：

方法一：

解题关键主要是想找到 num2 = target - num1 ,是否也在list中，就运用下面的方法：

• num2 in nums，返回 True 说明有戏
• nums.index(num2)，查找 num2 的索引

def twoSum(nums, target):
    lens = len(nums)
    j=-1
    for i in range(lens):
        if (target - nums[i]) in nums:
            if (nums.count(target - nums[i]) == 1)&(target - nums[i] == nums[i]):#如果num2=num1,且nums中只出现了一次，说明找到是num1本身。
                continue
            else:
                j = nums.index(target - nums[i],i+1) #index(x,i+1)是从num1后的序列后找num2                
                break
    if j>0:
        return [i,j]
    else:
        return []

执行通过但是耗时较长

方法二：

解题思路在方法一的基础上，优化解法。思想：num2并不需要每次都从nums里面查找一遍，只需要从num1之前或者之后查找即可。但为了方便index这里选择从num1位置之前查找：

def twoSum(nums, target):
    lens = len(nums)
    j = -1
    for i in range(1, lens):
        temp = nums[:i]
        if (target - nums[i]) in temp:
            j = temp.index(target - nums[i])
            break
    if j >= 0:
        return [j, i]

result = twoSum([1, 3, 5, 6, 9], 10)
print(result)

用字典模拟哈希进行求解：

参考了大神们的解法，通过哈希来求解，这里通过字典来模拟哈希查询的过程。
个人理解这种办法相较于方法一其实就是字典记录了 num1 和 num2 的值和位置，而省了再查找 num2 索引的步骤。

def twoSum(nums, target):
    
    hashmap = {}
    
    for ind, num in enumerate(nums):
        hashmap[num] = ind
        
    for i, num in enumerate(nums):
        j = hashmap.get(target-num)
        
        if j and i != j:
            return [i, j]

result = twoSum([2,11, 7, 15], 9)
print(result)

方法四：

类似方法二， num2 不需要在整个 dict 中去查找。可以在 num1 之前的 dict 中查找，因此就只需要一次循环可解决。

def twoSum(nums, target):

    hashmap = {}

    for i, num in enumerate(nums):
        if hashmap.get(target - num) is not None:
            return [i, hashmap.get(target - num)]

        hashmap[num] = i  # 这句不能放在if语句之前，解决list中有重复值或target-num=num的情况

result = twoSum([2,11, 7, 15], 9)
print(result)

与法三类似但是有点看不太懂。