替代的解決方案

假設你有整數的任意列表，並返回True如果在總計爲0替代的解決方案

我的列表中存在一對能夠產生n * log（n）複雜度的解決方案。這裏有一個簡短的草圖（雖然有一個更簡單的方法，見下文）：

排序數組。設置一個指向第一個元素的指針。
調查指針的元素（首先調用它）和元素在數組的對面（最後調用它）。如果第一個元素的大小大於最後一個元素的大小，請刪除第一個元素並將指針移至最後一個元素。否則開始遍歷數組向後尋找（可能的）總和。
如果沒有找到的總和，將指針指向下一個元素，並重復2

上面的解釋並不重要。 顯然還有另一種使用字典的解決方案。有人可以啓發我嗎？

不回答你的問題，但N *日誌的一個簡化版本（n）的算法是：1排序數組絕對值; 2.遍歷數組，檢查'a [i] == -a [i + 1]' – 2013-03-13 15:11:15

如果元素爲-x和x，則可以得到總和爲0。遍歷所有元素並將值存儲在字典中。如果你有一個x檢查是否設置了-x。

而且順便說一句，你的解決方案就是n *的log（n）+ N不是n *的log（n）通過使用HashMap的數據結構</nitpick> :)

2013-03-13 14:46:54 duedl0r

是不是O（n * lg（n）+ n）= O（n * lg（n））？ – 2013-03-13 14:54:29

我打賭@ JuanLopes的評論。 – 2013-03-13 14:57:36

您可以將key=n和value=0-n添加到字典中。如果字典已經包含0-n作爲鍵 - >找到了這對。

2013-03-13 14:45:52

可以輕鬆實現O（n）的時間/空間複雜度。

爲O（n）+ O（N）= O（n）的

2013-03-13 14:52:44 Roman

回答