列表data的值为[1, 3, 4, 5, 8, 9, 11],找出这个列表中和为13的两个数字的所有组合。这个好找,上过幼儿园大班的,估计都能找出来。4+9=13, 5+8=13。如何用python写一个函数来实现呢。
解法一:
超级大循环
最容易想到的就是遍历啊。嵌套循环,外层循环遍历全部列表,内层循环遍历当前元素位置之后的所有元素。内层循环中将两个数字相加,等于13就break。妥妥找到。
defequalSum01(data=None,twosum=13):result=[]fori,viinenumerate(data):ifi+1>len(data)-1:breakforj,vjinenumerate(data[i+1:]):ifvi+vj==twosum:print(vi,vj)result.append((vi,vj))breakreturnresult
解法二:
首尾相加法
因为data是升序排列的一个列表,我们可以用两个指针l, r指向列表的两端,那么data[l]+data[r]的和有3种情况:
1、等于S,那就将这两个数字添加的结果列表中,l指针右移,r指针左移
2、小于S, 将l指针右移
3、大于S, r指针左移
defequalSum02(data=None,twosum=13):result=[]l=0r=len(data)-1whilel<r:ifdata[l]+data[r]==twosum:result.append((data[l],data[r]))l+=1r-=1elifdata[l]+data[r]<twosum:l+=1else:r-=1returnresult
解法三:
精准搜索法
遍历data, 期待值 = S - data[i], 如果这个期待值在data[i]右面的剩余列表中,则找到,遍历万一遍,也就找到了所有的。
defequalSum03(data=None,twosum=13):result=[]fori,vinenumerate(data):if(twosum-v)indata[i+1:]:result.append((v,twosum-v))returnresult
从时间复杂度上来说,解法一是时间复杂度最大的一个。解法三因为每次循环都要搜索剩余的列表,应该大于解法二。
单元测试
importunittestclassTestInverseMethods(unittest.TestCase):deftest_equalSum01(self):data=[1,3,4,5,8,9,11]result=[(4,9),(5,8)]self.assertEqual(equalSum01(data),result)deftest_equalSum02(self):data=[1,3,4,5,8,9,11]result=[(4,9),(5,8)]self.assertEqual(equalSum02(data),result)deftest_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)