[LeetCode] 两数之和

2018-11-03  本文已影响0人  数据麻瓜

给定一个整数数组和一个目标值,找出数组中和为目标值的两个数。

nums=[2, 7, 11, 15], target = 9,
因为nums[0] + nums[1] = 2 + 7 = 9, return([0, 1]).

M1: 创建哈希表,然后检索target-nums[i]是否在哈希表中。因为python的dict就是基于哈希表,所以建立哈希表等统建创建dict

class Solution:      
    def twoSum(self, nums, target):     
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        d = {}  #create a hash table
        for i in range(len(nums)): #遍历list
            comp = target-nums[i]  #计算target-number
            if comp in d:  #如果comp和nums[i]相加等于target且都在nums这个list中,则返回对应索引
                return(d[comp],i)
            d[nums[i]] = i  #创建索引

结果: Runtime: 36 ms, faster than 99.68% of Python3 online submissions for Two Sum

Notes: 是否需要检索的话都可以用哈希表提高效率?

上一篇下一篇

猜你喜欢

热点阅读