python算法中双指针与哈希解题分析

1. 两数之和

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

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现

总结: 这题太重要了, 包含两种重要算法的思想

a. 利用双指针对有序数列前后相加与目标值比较, 通过向中间移动两个指针最终得到目标值, 死亡条件是两个指针重叠, 表示没有找到目标
b. 利用字典从头遍历,key=number, value=item, 如果target-numbers[item] in map.keys, 则找到的numbers[ map[target-numbers[item]] ] 与 numbers[item]就是结果

方法一：双循环

def twoSum(nums: List[int], target: int) -> List[int]:
    lens = (len(nums))
    for i in range(lens - 1):
        for j in range(i + 1, lens):
            if nums[i] + nums[j] == target:
                return [i, j]
 
    return []

两个for循环在我看来便是对双指针的初级用法。但显然，这里的双指针并不高效（O(n^2)），仅仅是作为一个启蒙式的运用而已

方式二：使用字典进行哈希查询

解题一：比较好理解

使用哈希表，可以将寻找 target - x 的时间复杂度降低到从 O(N)降低到 O(1)

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        result = list()
        dic = dict()
        for index, val in enumerate(nums):
            find = target - val
            if find in dic is not None:
                result = [dic[find], index]
                break
            else:
                dic[val] = index

        return result

用字典类型去存储列表时，一味地把列表下标当作key进行存储，导致get永远只能get到下标的对应的字符，从未想过反向存储，灵活运用get方法，通过字符去寻找对应下标。

此外，enumerate这个方法也值得记录，它对一次性遍历列表的字符和对应下标非常有用

解题二：不太好理解，但简洁

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        dict = {}   # 用字典查找与插入速度极快
        for i in range(len(nums)):  
            if target-nums[i] not in dict:  # 查找当前数是不是目标值加数中的一个
                dict[nums[i]] = i           # 不是，指针移动到下一个
            else:
                return [dict[target-nums[i]],i]   # 是的，返回剩余数的下标，这个数的下标

思路：
第一步：定义一个空的字典 d = {}
第二步：然后for循环遍历numbers 并且根据i逐一取出num
第三步：判断如果target - num的值不存在则将num和i放入dic中
第四步：如果target - num的值存在，则返回dic中key为target - num的值与i，结束