189 8069 5689

LeetCode怎么实现两数之和

这篇文章给大家分享的是有关LeetCode怎么实现两数之和的内容。小编觉得挺实用的,因此分享给大家做个参考,一起跟随小编过来看看吧。

专注于为中小企业提供成都网站设计、做网站、成都外贸网站建设公司服务,电脑端+手机端+微信端的三站合一,更高效的管理,为中小企业花垣免费做网站提供优质的服务。我们立足成都,凝聚了一批互联网行业人才,有力地推动了千余家企业的稳健成长,帮助中小企业通过网站建设实现规模扩充和转变。


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之前的值中查找符合条件的值,而不是针对列表中全部元素进行判断,使得效率进一步提升(不用担心这样会错过正确答案,因为当两个元素都循环到时,结果依旧可以识别出来)。


感谢各位的阅读!关于“LeetCode怎么实现两数之和”这篇文章就分享到这里了,希望以上内容可以对大家有一定的帮助,让大家可以学到更多知识,如果觉得文章不错,可以把它分享出去让更多的人看到吧!


当前文章:LeetCode怎么实现两数之和
当前网址:http://cdxtjz.cn/article/gosgge.html

其他资讯