Leecode刷题1——两数之和

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

你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

示例:

给定 nums = [2, 7, 11, 15], target = 9因为 nums[0] + nums[1] = 2 + 7 = 9所以返回 [0, 1]

 

python3解答：

class Solution:

    def twoSum(self, nums, target):

        """

        :type nums: List[int]

        :type target: int

        :rtype: List[int]

        """

        """

        暴力遍历，耗时高

        if not len(nums):

            return None

        for x in range(0,len(nums)):

            for y in range(0,len(nums)):

                if x == y:

                    continue

                if nums[x] + nums[y] == target:

                    return [x,y]

            return None

        """

        #用哈希表查找

        if not len(nums):

            return None

        hashmap = {}

        for x in range(0,len(nums)):

            com = target - nums[x]

            if com in hashmap.values():

                #根据值找键

                return [list(hashmap.values()).index(com),x]  

#com在hashmap.values()中的索引就是对应字典里的key值，所以不用再查找hashmap.keys()

            hashmap[x] = nums[x]

        return None

 

 

最优解使用哈希表查询，将列表nums的元素跟索引插入字典作为键值对，在插入字典前先判断字典中是否存在等于target减去当前元素值（target - nums[x]）的值，若存在直接返回当前元素的索引跟字典中符合条件的值的键。

通过值获取字典中的键：

list(mydict.keys())[list(mydict.values()).index(2)]

python3中mydict.values()和mydict.keys()返回一个<class 'dict_values'>，使用list()转换为列表，keys跟values的元素索引一一对应。list(mydict.values()).index(2)返回值为2的索引，利用该索引找到对应的key值:list(mydict.keys())[index]。

PS：python2中mydict.values()和mydict.keys()返回一个列表，无需强制转换。