VB.net 2010 视频教程 VB.net 2010 视频教程 python基础视频教程
SQL Server 2008 视频教程 c#入门经典教程 Visual Basic从门到精通视频教程
当前位置:
首页 > 编程开发 > python爬虫 >
  • python爬虫之LeetCode | No.1 两数之和

本站最新发布   Python从入门到精通|Python基础教程
试听地址  
https://www.xin3721.com/eschool/python.html


题目描述:

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.

 

给定一个整数数组nums和一个目标值target,请你在该数组中找出和为目标值的那两个整数,并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是你不能重复利用这个数组中同样的元素。

示例:

复制代码
1 给定 nums = [2, 7, 11, 15], target = 9
2 
3 因为 nums[0] + nums[1] = 2 + 7 = 9
4 所以返回 [0, 1]
5 
6 来源:力扣(LeetCode)
复制代码

本题的难度在力扣中显示为简单,其本身也的确不难。拿到题后的第一个想法就是疯狂遍历,必定有列表中的两数之和与目标值相等,两数相加也就需要两层循环而已。

1 for i in range(len(nums)):
2     for j in range(i+1, len(nums)):
3         if nums[i] + nums[j] == target:
4             return list([i, j])

显然本题的数据量很少,感觉不到慢多少,但是如果利用time库计算下其计算时间,该方案并不是最佳的。这时候就可以体会到Python的强大之处了。Python中有很多出人意料的语法,就像(A)in(B)表示(A)在(B)中这样的,简直和我们生活中说话一样,为了降低复杂度,我就开始想着减少一层循环。看一下下面这段程序:

复制代码
 1 class Solution:
 2     def twoSum(self, nums, target):
 3         """
 4         :type nums: List[int]
 5         :type target: int
 6         :rtype: List[int]
 7         """
 8         for i in nums:
 9             n = target - i
10             if n in nums and nums.index(n) != nums.index(i):
11                 return [nums.index(i),nums.index(n)]
复制代码

是不是仅用一层循环就解决问题了呢。的确复杂度是降下来了,但是当我提交的时候出问题了。再看一遍程序发现,这里没有判断两个数相等的情况。Python中有一个数据类型是字典,也就是通过索引来定位数据。同时字典也有很多它自身的属性和方法,可以和方便的找到内容所对应的索引。对上面的错误进行了改进之后为:

复制代码
 1 class Solution:
 2     def twoSum(self, nums, target):
 3         """
 4         :type nums: List[int]
 5         :type target: int
 6         :rtype: List[int]
 7         """
 8         dic1 = {nums[i]:i for i in range(len(nums))}
 9         dic2 = {i:target-nums[i] for i in range(len(nums))}
10         for i in range(len(nums)):
11             j = dic1.get(dic2.get(i))
12             if j and j != i:
13                 return [i,j] 
复制代码
终于,测试通过了,同时复杂度也相对暴力破解更低一些。
 
相关教程