3

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

我能够产生 n*log(n) 复杂度的解决方案。这是一个简短的草图（虽然有一个更简单的方法，见下文）：

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

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

4

3 回答 3

3

如果元素是 -x 和 x，则总和可以得到 0。遍历所有元素并将值存储在字典中。如果您有 x 检查是否设置了 -x。

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

于 2013-03-13T14:46:54.183 回答
1

您将key=n和添加value=0-n到字典中。如果字典已经包含0-n作为键 -> 找到该对。

于 2013-03-13T14:45:52.920 回答
1

您可以通过使用 hashmap 数据结构轻松实现 O(n) 时间/空间复杂度。

  1. 遍历所有元素并将它们放入 hashmap（时间复杂度为 O(n)，考虑到 hashmap 操作插入、查找和删除的分摊时间复杂度为 O(1)）
  2. 遍历所有元素并为每一个元素检查hashmap 是否包含逆值（即，对于每个值V 检查，如果hashmap 包含-V 值）。时间复杂度再次为 O(n)。

O(n) + O(n) = O(n)

于 2013-03-13T14:52:44.100 回答