ITPub博客

首页 > > > 计算机面试刷题——「算法」两数之和

计算机面试刷题——「算法」两数之和

作者:choubou 时间:2019-12-12 15:42:51 0 删除 编辑

题目如下:

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

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

实例如下:

题目实例

分析:

题目对答题有所限制,首先是解中包含两个数组元素不同索引(下标),可以是不同位置的相同的两个数为解的情况,但能是相同位置的同一个数为解的情况,即是nums[0]+nums[1]=1+1=2的情况,但不能是nums[0]+nums[0]=1+1=2这种情况。而且对于每一个输入只有一个解,意味着上述实例中的解只能是[0,1]而不能是[1,0]。

(为什么不能是[1,0]?既然实例的答案是从小到大排列,那么自己的答案也应该这样排列,按照出题人的思维来就行了2333)

另外由于最朴素的暴力发遍历搜索具有O(n^2)的时间复杂度,所以不再考虑范围之内。

附上Python的参考代码(由于手机看代码块比较乱,我就直接插图了):

Python代码及注释

函数定义之后的'->'符号指明预期接受的返回值的类型,list.index返回第一个res的索引,list.count属性统计列表中的某个元素的个数,如果另一个解和当前元素相等且当前元素有多个,那么继续搜索另一个,#如果另一个解和当前元素相等,但只有当前元素一个,那么不再继续搜索。

运行结果如下:

题目实例的运行结果

接着提交代码,运行通过,执行时间1044ms,内存消耗13.6MB。

在这道题的评论中找到了另一种使用字典的方法,此方法无论是运行速度还是内存消耗都优于第一种方法:

使用字典的方法

此方法运行通过,执行时间64ms,内存消耗13.1MB。

来自 “ ITPUB博客 ” ,链接:https://blog.itpub.net/4548/viewspace-3169811/ ,如需转载,请注明出处,否则将追究法律责任。

上一篇: css盒子练习3
下一篇: 没有了~
请登录后发表评论 登录
全部评论

注册时间:2019-10-08

  • 博文量
    175
  • 访问量
    10707