题目如下:
给定一个整数数组 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。