绑定完请刷新页面
取消
刷新

分享好友

×
取消 复制
计算机面试刷题——「算法」两数之和
2019-12-12 15:42:51

题目如下:

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

分享好友

分享这个小栈给你的朋友们,一起进步吧。

未知元素
创建时间:2019-11-10 22:02:06
未知元素
展开
订阅须知

• 所有用户可根据关注领域订阅专区或所有专区

• 付费订阅:虚拟交易,一经交易不退款;若特殊情况,可3日内客服咨询

• 专区发布评论属默认订阅所评论专区(除付费小栈外)

栈主、嘉宾

查看更多
  • xiechundi
    栈主

小栈成员

查看更多
  • 渔人
  • abc
  • zyl
  • ?
戳我,来吐槽~