Python算法题----在列表中找到和为s的两个数字
列表data的值为，找出这个列表中和为13的两个数字的所有组合。这个好找，上过幼儿园大班的，估计都能找出来。4+9=13, 5+8=13。如何用python写一个函数来实现呢。解法一：超级大循环
最容易想到的就是遍历啊。嵌套循环，外层循环遍历全部列表，内层循环遍历当前元素位置之后的所有元素。内层循环中将两个数字相加，等于13就break。妥妥找到。
1
2
3
4
5
6
7
8
9
10
11
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):
if vi + vj == twosum:
print(vi, vj)
result.append((vi, vj))
break
return result
解法二：
首尾相加法
因为data是升序排列的一个列表，我们可以用两个指针l, r指向列表的两端，那么data+data的和有3种情况：
1、等于S，那就将这两个数字添加的结果列表中，l指针右移，r指针左移
2、小于S, 将l指针右移
3、大于S, r指针左移
1
2
3
4
5
6
7
8
9
10
11
12
13
14
def equalSum02(data=None, twosum=13):
result = []
l = 0
r = len(data) - 1
while l < r:
if data + data == twosum:
result.append((data, data))
l += 1
r -= 1
elif data + data < twosum:
l += 1
else:
r -= 1
return result
解法三：
精准搜索法
遍历data, 期待值 = S - data， 如果这个期待值在data右面的剩余列表中，则找到，遍历万一遍，也就找到了所有的。
1
2
3
4
5
6
def equalSum03(data=None, twosum=13):
result = []
for i, v in enumerate(data):
if (twosum - v) in data:
result.append((v, twosum - v))
return result
从时间复杂度上来说，解法一是时间复杂度最大的一个。解法三因为每次循环都要搜索剩余的列表，应该大于解法二。
单元测试
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import unittest
class TestInverseMethods(unittest.TestCase):
def test_equalSum01(self):
data =
result = [(4, 9), (5, 8)]
self.assertEqual(equalSum01(data), result)
def test_equalSum02(self):
data =
result = [(4, 9), (5, 8)]
self.assertEqual(equalSum02(data), result)
def test_equalSum03(self):
data =
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)
页:
[1]