? ? 列表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:breakfor?j,?vj?in?enumerate(data[i+1:]):if?vi?+?vj?==?twosum:print(vi,?vj)result.append((vi,?vj))breakreturn?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?=?0r?=?len(data)?-?1while?l?<?r:if?data[l]?+?data[r]?==?twosum:result.append((data[l],?data[r]))l?+=?1r?-=?1elif?data[l]?+?data[r]?<?twosum:l?+=?1else:r?-=?1return?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?unittestclass?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)

總結

以上是生活随笔為你收集整理的Python算法题----在列表中找到和为s的两个数字的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。