LeeCode1:两数之和

Python publisher01 26℃ 0评论

问题:

给定一个整数数组 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

“`

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

转载请注明:Python量化投资 » LeeCode1:两数之和

喜欢 (0)or分享 (0)
发表我的评论
取消评论
表情

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址