LeetCode刷题DAY 8：两数之和

看似简单的一道题目，但要是想提升代码效率还是要费点脑筋。

1

题目描述

给定一个整数数组 nums 和一个目标值 target，在该数组中找出和为目标值的那两个整数的数组下标。如nums = [2, 7, 11, 15], target = 9时，返回[0,1](因为2+7=9)。

2

解题

思路一：遍历匹配

通过两层for循环对所有可能逐一进行验证，找到正确结果。此方法python程序在LeetCode中显示时间超出限制，不推荐。

思路二：哈希表

通过一层for循环结合enumerate()找到每个数字值与位置的关系，存储在哈希表中。因为要找两数之和，所以每次循环时，首先判断target-item是否在已经建立的哈希表中，如果在则返回两个值的位置，如果不在把本次得到的值与位置关系新添在哈希表中。

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        h_map = {} # 或 h_map = dict()
        for i,item in enumerate(nums):
            if target-item in h_map : 
            # 或 if h_map.get(target-item) is not None: ,
            # 但速度略慢一些
                return [h_map[target-item],i]
            h_map[item]=i

需要注意的是，类似nums=[2，2]，target=4的输入，生成哈希表时第二个2的位置会覆盖第一个2的位置，导致无法得到[0，1]的结果，因此要在循环最后将本次的值与位置关系加入哈希表中，而不是在两层for后首先将对应关系加入哈希表。并且本方法，判断target-item是否在列表中时，是在item之前的值中查找符合条件的值，而不是针对列表中全部元素进行判断，使得效率进一步提升(不用担心这样会错过正确答案，因为当两个元素都循环到时，结果依旧可以识别出来)。