欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Python算法题----在列表中找到和为s的两个数字

程序员文章站 2022-03-13 12:27:05
...

    列表data的值为[1, 3, 4, 5, 8, 9, 11],找出这个列表中和为13的两个数字的所有组合。这个好找,上过幼儿园大班的,估计都能找出来。4+9=13, 5+8=13。如何用python写一个函数来实现呢。

解法一:

超级大循环

最容易想到的就是遍历啊。嵌套循环,外层循环遍历全部列表,内层循环遍历当前元素位置之后的所有元素。内层循环中将两个数字相加,等于13就break。妥妥找到。

def equalSum01(data=None, twosum=13):
    result = []
    for i, vi in enumerate(data):
        if i + 1 > len(data) - 1:
            break
        for j, vj in enumerate(data[i+1:]):
            if vi + vj == twosum:
                print(vi, vj)
                result.append((vi, vj))
                break
    return result


解法二:

首尾相加法

因为data是升序排列的一个列表,我们可以用两个指针l, r指向列表的两端,那么data[l]+data[r]的和有3种情况:

1、等于S,那就将这两个数字添加的结果列表中,l指针右移,r指针左移

2、小于S, 将l指针右移

3、大于S, r指针左移

def equalSum02(data=None, twosum=13):
    result = []
    l = 0
    r = len(data) - 1
    while l < r:
        if data[l] + data[r] == twosum:
            result.append((data[l], data[r]))
            l += 1
            r -= 1
        elif data[l] + data[r] < twosum:
            l += 1
        else:
            r -= 1
    return result


解法三:

精准搜索法

遍历data, 期待值 = S - data[i], 如果这个期待值在data[i]右面的剩余列表中,则找到,遍历万一遍,也就找到了所有的。

def equalSum03(data=None, twosum=13):
    result = []
    for i, v in enumerate(data):
        if (twosum - v) in data[i+1:]:
            result.append((v, twosum - v))
    return result


从时间复杂度上来说,解法一是时间复杂度最大的一个。解法三因为每次循环都要搜索剩余的列表,应该大于解法二。


单元测试

import unittest

class TestInverseMethods(unittest.TestCase):
    
    def test_equalSum01(self):
        data = [1, 3, 4, 5, 8, 9, 11]
        result = [(4, 9), (5, 8)]
        self.assertEqual(equalSum01(data), result)
        
    def test_equalSum02(self):
        data = [1, 3, 4, 5, 8, 9, 11]
        result = [(4, 9), (5, 8)]
        self.assertEqual(equalSum02(data), result)
        
    def test_equalSum03(self):
        data = [1, 3, 4, 5, 8, 9, 11]
        result = [(4, 9), (5, 8)]
        self.assertEqual(equalSum03(data), result)
        
if __name__ == ‘__main__‘:
    unittest.main()


...

----------------------------------------------------------------------

Ran 3 tests in 0.000s


OK

(4, 9)

(5, 8)