algorithm - "Determine if list contains two ints that sum to 0"的替代解决方案

Question

假设您有一个任意整数列表，如果列表中存在一对总和为 0 的值，则返回 True。

我能够生成 n*log(n) 复杂度的解决方案。这是一个简短的草图(尽管有更简单的方法，请参见下文):

1. 对数组进行排序。设置指向第一个元素的指针。
2. 调查指针的元素(最先调用)和数组对面的元素(最后调用)。如果第一个元素的大小大于最后一个元素，则删除第一个元素并将指针移动到最后一个元素。否则开始向后遍历数组以寻找(可能的)总和。
3. 如果没有找到和，将指针移动到下一个元素并重复 2。

上面的解释并不重要。 显然还有另一种使用字典的解决方案。有人可以启发我吗？

Answer 1

如果元素为 -x 和 x，则总和为 0。遍历所有元素并将值存储在字典中。如果你有一个 x 检查是否设置了 -x。

顺便说一句，您的解决方案是 n*log(n)+n 而不是 n*log(n) </nitpick> :)