大家好,又见面了,我是你们的朋友全栈君。
题目描述:
写一个函数,此函数要实现以下功能:
给一个列表,并且给一个目标数字,如果列表里的两个数字之和等于目标数字,返回那两个数字的索引值。
比如,给定列表[3,5,7,14],目标数字是10,那么返回[0,2],0是3的索引,2是7的索引,3+7=10.
注意,不可以重复利用列表中的某个数字,比如返回[1,1]是不能接受的。
一、两层for循环遍历列表
思路:先拿出列表里的第0个数字,依次尝试和第1个、第2个……第n个相加,看能否等于目标数字,如果有某个组合等于目标数字,就返回这个组合的两个索引值,如果都不行,再拿出第1个数字,依次尝试和第2个、第3个……第n个相加,看能否等于目标数字……每个数字都不需要回过头和前面的数字相加,因为之前已经尝试过了。
这种方法的思路非常简单,但是算法的时间复杂读比较高,为O(n2),当给定的列表很长的时候,耗时非常长。
#nums参数需要一个列表,target参数就是我们想实现的和的值
def twoIndices(nums,target):
'''这是寻找和为目标值的两个数的索引的函数'''
for i in range(len(nums)):
#我们不需要回过头相加,所以j是从i的下一个数字开始,到列表的末尾
for j in range(i+1,len(nums)):
if nums[i]+nums[j]==target:
return [i,j]
else:
return "No such two numbers."
#这是我们用来检测上述函数是否好用的一个例子
print(twoIndices([3,6,3,5],6))
二、用字典来实现
思路:
先建立一个用于存放数字和索引的空字典。
我们从列表中取出一个数字,然后看字典里是否存在能跟这个数字相加得到目标数字的数字。如果存在,就返回两个数字的索引,不存在,就把取出来的这个数字作为键,它的索引作为值存进字典,并取出下一个数字,重复刚才的操作,直到找到合适的两个数字或者全部数字都看过一遍为止。
这样算法的时间复杂度是O(n),比第一种方法好多了。
#nums参数需要一个列表,target参数就是我们想实现的和的值
def twoIndices(nums,target):
'''这是寻找和为目标值的两个数的索引的函数'''
#定义一个用于存放数字和索引的字典
mydict={}
#遍历列表里的数字,得到索引和数字
for index,right_num in enumerate(nums):
#用目标数字减去我们当前从列表中取出的数字,得到我们需要的数字
left_num=target-right_num
#如果字典里已经存放了我们需要的数字
if mydict.get(left_num) != None:
#返回我们需要的数字的索引和当前数字的索引,终止循环
return [mydict[left_num],index]
#如果字典里还不存在我们需要的数字,则把当前的数字和它的索引存入字典
mydict[right_num]=index
else:
return 'No such two numbers.'
#用这个列表测试我们的函数好不好用
print(twoIndices([3,5,3,8],6))
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/137833.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...