前些日子有個朋友問我一個問題， 有某架飛機起飛前的重量， 距離最大載重還有 150 公斤， 地勤人員想要從登記候補機位的旅客中，找出兩個旅客體重的和剛好等於 150 公斤來把飛機塞滿， 請問地勤人員有沒有甚麼好方法可以解決這個問題？ 我聽到這個問題之後， 突然想起 Two Number Sum 這個演算法問題。
說實在的， Two Number Sum, Three Number Sum, …, N Number Sum 問題， 過去在書上或是面試的試卷上， 看到這些問題的時候， 總是很直覺地就進入怎麼用程式解決這種問題， 從來也沒想過在實際生活上可以發揮甚麼作用， 沒想到朋友這麼一問， 當下就讓我驚覺如果不是朋友神來一問， 我還真的就只是停留在知其所以， 而不知其所以然， 不知為誰而戰， 為何而戰的處境而不自知了， 想來就覺得慚愧。
方法 1 – 迴圈法
這是最直覺的方法， 利用兩個迴圈， 把給定的數值兩兩相加之後， 找出第一個滿足相加的結果等於所求數值， 就可以解決這個問題。
def twoNumberSum(numberArray, targetSum):
for i in range(len(numberArray) - 1):
firstNumber = numberArray[i]
for j in range(i + 1, len(numberArray)):
secondNumber = numberArray[j]
if firstNumber + secondNumber == targetSum:
return [firstNumber, secondNumber]
return []
na = [3, 5, -4, 8, 11, 1, -1, 6]
ts = 10
found = twoNumberSum(na, ts)
if len(found) > 0:
print('found:', *found)
else:
print('not found!')
這個方法的 time complexity 是 O(n^2) ， space complexity 是 O(1) 。
方法二、雜湊法 (字典法)
利用資料結構中所介紹的雜湊表 (Hash Table) ，我們從一個空的雜湊表開始， 依序將給定的數值拿出來與所求數值相比較， 看看在雜湊表中有沒有剛好等於兩者之差的數值， 如果有的話那現在與所求數值比較地給定數值， 與雜湊表中存在的差值數值就是我們要找的兩個數值。
def twoNumberSum(numberArray, targetSum):
numberHashTable = {}
for currentNumber in numberArray:
potentialNumber = targetSum - currentNumber
if potentialNumber in numberHashTable:
return [potentialNumber, currentNumber]
else:
numberHashTable[currentNumber] = True
return []
na = [3, 5, -4, 8, 11, 1, -1, 6]
ts = 10
found = twoNumberSum(na, ts)
if len(found) > 0:
print('found:', *found)
else:
print('not found!')這個方法的 time complexity 是 O(n) ， space complexity 是 O(n) 。
方法三、排序法
利用足夠好的排序演算法， 我們可以先將給定的數值由小到大升冪排序， 由最左邊與最右邊取出兩個數值來相加， 如果相加之值剛好等於所求之值， 那麼目前左、右這兩個數值就是問題的解答。 否則， 如果相加之值比較小， 表示我們要把左邊的數， 往剛剛好比它大的下一個數移動； 反之， 如果相加之值比較大， 就表示我們要把右邊的數， 往剛剛比它小的下一個數移動， 再重新加總與所求之值進行檢查， 如此反覆進行此過程， 一直到左邊與右邊這兩個用來取得數值的索引， 互相超過對方為止， 如果都沒有找到相加符合所求之值的數值， 就表示我們把給定的數值全部都計算過了之後， 找不到問題所要的答案。
def twoNumberSum(numberArray, targetSum):
numberArray.sort()
leftIndex = 0
rightIndex = len(numberArray) - 1
while leftIndex < rightIndex:
currentSum = numberArray[leftIndex] + numberArray[rightIndex]
if currentSum == targetSum:
return [numberArray[leftIndex], numberArray[rightIndex]]
elif currentSum < targetSum:
leftIndex += 1
elif currentSum > targetSum:
rightIndex -= 1
return []
na = [3, 5, -4, 8, 11, 1, -1, 6]
ts = 10
found = twoNumberSum(na, ts)
if len(found) > 0:
print('found:', *found)
else:
print('not found!')這個方法的 time complexity 是 O(n log(n)) ， space complexity 是 O(1) 。
討論
如果朋友會寫程式， 那麼我把這一篇的內容跟朋友說明清楚之後， 就可以解決問題。 麻煩的是這位朋友並不會寫程式， 因此我必須得提供其他的方式。 還好我當天頭腦還算清楚， 馬上又聯想到這個問題好像跟 Excel 試算表的規劃求解問題有點類似的樣子喔， 於是乎就又勾起那段常常使用 Excel 試算表的往日回憶。
後來仔細想想， 其他與朋友所提問題類似的生活問題，應該也都可以使用這個演算法來求解， 例如：
- 菜市場豬肉攤老闆賣肉的過程中， 產生了許多不同重量的豬肉塊， 有 200g， 400g 等等各種不同重量的豬肉塊， 豬肉攤老闆也都分門別類地把它們都整理好放在攤位上， 現在有一個顧客跑來要跟老闆買總重 700 公克的豬肉， 請問老闆有沒有甚麼好方法挑出 2 塊先前已經切好的豬肉塊， 包裝在一起賣給客人呢？
- 工廠每半天生產出來的成品， 就會在休息的時候， 計算通過品保的成品數量， 然後把它們包裝成一袋， 送到倉庫去存放管理。 現在有一張客戶的訂單要購買某個數量， 老闆規定倉庫的管理人員去找出兩袋成品數量符合該客戶訂單數量， 好出貨給該客戶， 請問倉管人員有沒有甚麼好的方法挑出符合訂單數量的兩袋成品呢？
- BBC Earth 頻道 Inside the Factory (工廠走透透) 節目中， 提到馬鈴薯片包裝的時後， 馬鈴薯片從輸送帶上， 掉入 12 個秤重漏斗中， 然後電腦程式再從中挑選 2 個 (或 3 、 4 個) 剛好符合 25g 的漏斗開啟， 將其中的薯片掉入包裝袋封裝成一袋， 生產線的員工提到整個秤重、開啟、包裝過程只要 30ms 。
- … (其他有碰到， 有想到就繼續補在這邊， 或是要提供生活例子也可以跟作者聯繫喔， 謝謝囉)