排序找到目標對

Question

嗨，大家好，我發現在一本書中的排序這個有趣的應用：

查找目標對 - 我們如何測試是否存在兩個整數x，集合S這樣的y成員對於某個目標z，x + y = z？而不是測試所有可能的配對，按升序和掃描對數字進行排序。隨着S [i]隨i增大，其可能的夥伴j使得S [j] = z-S [i]減小。因此，當我增加時適當地減少j是一個很好的解決方案

我花了很多時間試圖弄清楚這種排序的應用程序如何工作，但無法做到這一點。你能幫忙嗎？

Answer 1

想象這一套：

[1, 2, 4, 6, 7, 8, 10, 13, 14, 17] 

你必須找到號碼的這一套使得x+y = 17一對x, y。

如果您的設置未排序，您可以檢查每個可能的對，這是很長的（具有O（n2）複雜度）。

如果您設置的排序，你可以與第一和最後一個號碼爲x和y啓動，並通過一組通過增加x和減少y移動：

1 + 17 --> Too big --> Decrease y 
1 + 14 --> Too small --> Increase x 
2 + 14 --> Too small --> Increase x 
4 + 14 --> Too big --> Decrease y 
4 + 13 = 17. STOP, you found a pair! 

這有一個O（nlogn ）排序的複雜性，以及尋找對的O（n）複雜度。