Python教程网
--左手Python,右手AI!

Leetcode刷题笔记——No.1 两数之和

原题:

Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
题目大意:给出一个数字列表和一个目标值(target),假设列表中有且仅有两个数相加等于目标值,我们要做的就是找到这两个数,并返回他们的索引值。

例如:

Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

小詹第一反应就是两层循环就可以解决,小case,的确思路简单,但是时间复杂度,你懂得!很简单就能想到的代码如下:

def twoSum(self, nums, target):
    """
    :type nums: List[int]
    :type target: int
    :rtype: List[int]
    """
    result = []
    for i in range(len(nums)):
       for j in range(i+1, len(nums)):
           if nums[i] + nums[j] == target:
               result.append(i)
               result.append(j)
               return result

其实这里也可以用一层循环即可实现,因为我们知道有且仅有一个解;我们可以通过判断target与某一个元素的差值是否也在列表之中即可,这个和两层循环思路类似,但是不难想到计算次数就下降了,代码如下:

def twoSum(self, nums, target):
    """
    :type nums: List[int]
    :type target: int
    :rtype: List[int]
    """
    result = []
    for i in range(len(nums)):
       oneNum = nums[i]
       twoNum  = target - oneNum
       if twoNum in nums:
          j = nums.index(twoNum)
          if i != j:
             result.append(i)
             result.append(j)
             return result

的确两种方案都轻松通过了,but用时过长,排名老靠后了。之后小詹在网上找到了另一种方案,整体思路和一层循环的方案二有点类似:通过创建字典,将nums里的值和序号对应起来,并创建另一个字典存储目标值(Target)-nums的值,通过判断该值是否在nums内进行判断并返回其对应索引值,代码如下:

def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        # 创建字典一,存储输入列表的元素值和对应索引
        num_dict = {nums[i]:i for i in range(len(nums))}
        print(num_dict)
        # 创建另一个字典,存储target-列表中的元素的值,小詹称为num_r吧,好表达
        num_dict2 = {i:target-nums[i] for i in range(len(nums))}
        print(num_dict2)
        # 判断num_r是否是输入列表中的元素,如果是返回索引值,不是则往下进行
        result = []
        for i in range(len(nums)):
            j = num_dict.get(num_dict2.get(i))
            if (j is not None) and (j!=i):
                result = [i,j]
                break
        return result

该方案,在时间效率上还较为理想,小詹亲测结果排名beat 62%.

原文首发于公众号小詹学Python,点击此处查看原文

欢迎扫码关注!

赞(2)
未经允许不得转载:Python教程网 » Leetcode刷题笔记——No.1 两数之和
分享到: 更多 (0)

评论 20

  1. #1

    It can also be transferred from an infected mother to her
    unborn child. saleviabuy.com viagra otc

    匿名4周前 (10-30)回复
  2. #2

    catholics on viagra shelf life of viagra pills ejaculate with viagra

    匿名2周前 (11-16)回复
  3. #3

    generic viagra online next day shipping viagra 50mg online viagra australian

    匿名2周前 (11-16)回复
  4. #4

    п»їviagra online wallmart price viagra viagra n line

    匿名2周前 (11-16)回复
  5. #5

    viagra gold 365 https://paradiseviagira.com/ mastercard that accept viagra top of the line

    匿名2周前 (11-16)回复
  6. #6

    viagra pills offers purevigra.com herbal viagra dosierung

    匿名1周前 (11-17)回复
  7. #7

    buy viagra without prescription viagra online? viagra paypal

    匿名1周前 (11-17)回复
  8. #8

    banned viagra videos purevigra.com frederik fetterlein viagra

    匿名1周前 (11-17)回复
  9. #9

    getting prescriptions for viagra https://buybuyviamen.com/ viagra and mental health

    匿名1周前 (11-19)回复
  10. #10

    buying egypt viagra viagra online australia viagra u

    匿名1周前 (11-19)回复
  11. #11

    viagra ses effets https://buybuyviamen.com zum spaГџ viagra nehmen

    匿名1周前 (11-19)回复
  12. #12

    viagra pfizer Г¶sterreich viagra diaries wiki il viagra aumenta la durata

    匿名1周前 (11-20)回复
  13. #13

    buy viagra australia canadian viagra coupon where can i get viagra

    匿名6天前回复
  14. #14

    sildenafil 100mg cheap sildenafil 50 mg online us buy viagra with paypal australia

    匿名6天前回复
  15. #15

    female viagra over the counter online order viagra in india cheap viagra australia fast delivery

    匿名6天前回复
  16. #16

    viagra 100mg price canada female viagra price india buy sildenafil canada

    匿名6天前回复
  17. #17

    canadian online pharmacy sildenafil cheap viagra wholesale viagra uk cost

    匿名2天前回复
  18. #18

    viagra cost in australia buy viagra brand female viagra online order

    匿名2天前回复
  19. #19

    viagra online australia paypal viagra sydney viagra with paypal payment option

    匿名1天前回复
  20. #20

    online viagra tablet canada purchase viagra from canada where to buy cheap viagra pills

    匿名17小时前回复