Python求解两数之和[通俗易懂]

全栈程序员站长

发布于 2022-08-22 15:46:24

6200

文章被收录于专栏：全栈程序员必看全栈程序员必看

大家好，又见面了，我是你们的朋友全栈君。

题目描述：

写一个函数，此函数要实现以下功能：

给一个列表，并且给一个目标数字，如果列表里的两个数字之和等于目标数字，返回那两个数字的索引值。

比如，给定列表[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))

发布者：全栈程序员栈长，转载请注明出处：https://javaforall.cn/137833.html原文链接：https://javaforall.cn

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2022年5月5，如有侵权请联系 cloudcommunity@tencent.com 删除

java