LeeCode1:两数之和

问题:

给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。你可以假设每种输入只会对应一个答案。但是,你不能重复利用这个数组中同样的元素。

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9

所以返回 [0, 1]


解题:

首先,面对这道题,我们最好不要使用nums[inedx_1] + nums[index_2] = target的方式。

因为,每次迭代都会进行一遍加法计算,会增大cpu计算量。

所以,采用temp_target = target – nums[index_1]的方式,寻找temp_target。

最简单的解题方法是暴力双循环,但是时间复杂度是O(n^2)

减少时间复杂度的方法,可以使用哈希表,即python中的字典。

先进行迭代,并将value和index传入字典中,为了方便起见,可以将value作为字典的索引值,index作为字典的内容,即可获得下面算法代码:

“`

class Solution:

    def twoSum(self, nums: List[int], target: int) -> List[int]:

        dict = {}

        for index,value in enumerate(nums):

            diff = target – value

            if diff in dict:

                return [dict[diff],index]

            else:

                dict[value] = index

“`

你或许想:《去原作者写文章的地方

「点点赞赏,手留余香」

    还没有人赞赏,快来当第一个赞赏的人吧!
0 条回复 A 作者 M 管理员
    所有的伟大,都源于一个勇敢的开始!
欢迎您,新朋友,感谢参与互动!欢迎您 {{author}},您在本站有{{commentsCount}}条评论