替代的解决方案

假设你有整数的任意列表，并返回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

回答