檢索加到列表中的目標的所有數字對

-4

假設我有一個列表[1,2,3,4,4]和一個目標5。我需要找到總和爲5的所有對，即(1,4),(1,4),(2,3)。有人可以建議我一個算法如何解決它在不到O(n^2)。我在準備面試的時候會看到這個問題，但我無法在小於O(n^2)的範圍內解決問題。任何幫助表示讚賞檢索加到列表中的目標的所有數字對

來源

2017-03-02 Code-Ninja

你需要顯示在第一解決這個_your_嘗試。 –

瞭解有關哈希映射的更多信息，然後嘗試。 – Shashank

我試着比較一個元素與所有元素 –

嗯，讓我顯示想法，你會實現吧，好不好？

第一階段。建立一個字典（地圖）其中key = number,value = number's occurrencies。例如。對於[1, 2, 3, 4, 4]我們應該有

{1, 1}, // we have exactly one 1 
{2, 1}, //    -/- 2 
{3, 1}, //    -/- 3 
{4, 2} //   we have two 4's

您可以創建這樣一個字典中線性時間O(N)。

第二階段。掃描陣列，對於每個item查看字典中的key = 5 - item並重復 (item, 5 - item)對value次。例如。對於[1,2,3,4,4]我們將有

item | key | value | output 
----------------------------------- 
    1 | 4 |  2 | (1, 4), (1, 4) 
    2 | 3 |  1 | (2, 3) 
    3 | 2 |  1 | (3, 2) 
    4 | 1 |  1 | (4, 1) 
    4 | 1 |  1 | (4, 1)

正如你所看到的第二個階段，也O(N)

來源

2017-03-02 19:27:41

謝謝你這麼多先生 –

檢索加到列表中的目標的所有數字對

回答

相關問題