在一个数组中找到两个元素，它们的和为k。

Question

可能重复:
给定两个数组a和b。找到所有元素对(a1，b1)，使得a1属于数组A，b1属于数组B，其总和a1+b1=k。

给定：一个未排序的整数数组A
输入：一个整数k

输出：所有元素之和等于k的两个元素集合，时间复杂度为O(n)。

示例：

A = {3,4,5,1,4,2}

输入：6
输出：{3,3}，{5,1}，{4,2}

注意：我知道一种O(n logn)的解决方案，但那需要将数组排序。是否有任何方法可以在O(n)中解决这个问题？可以使用非平凡的C++数据结构，即空间没有限制。

- Debanjan Chanda

---

你是如何得出输出数组对 {3,3} 的？输入数组中只有一个3。 - Sanjeevakumar Hiremath

负元素允许吗？ - Ben Voigt

你的数组A中只有一个值为3。{3,3}仍然是解集的一部分吗？ - Paul Hanbury

不允许负数 @Ben Voigt。 - Debanjan Chanda

Answer 1

创建一个常数时间查找表（哈希表），以便您可以查看特定整数是否包含在数组中（O(n)）。然后，对于数组中的每个元素，请查看是否包含k-A[i]。对于每个元素，这需要恒定的时间，因此总共需要O(n)的时间。这假设元素是不同的；如果有重复元素，也不难使其正常工作。

- user684934

---

从技术上讲，除了完美的哈希函数外，哈希表的平摊时间复杂度仅为O(1)。尽管这是一个聪明的解决方案。但如果问题是“3”可以使用两次吗，则必须在哈希构建过程中计算每个成员。 - edA-qa mort-ora-y

根据问题，空间没有任何限制，而这是C ++，其中整数通常是有界的，因此您拥有完美的哈希函数 - 恒等函数。您只需要一个超级巨大的哈希表（实际上是查找表），它需要非常大但恒定的时间来初始化！ Tada！ ;) 这证明了复杂性分析可能会误导人，特别是当您假设内存无限时。 - Robin Green

@Robin 哈希函数与恒等函数不同，因为它确实是根据输入数量线性的。恒等函数仅限于整数，并且需要与最小和最大元素之间的间隔一样长的时间；它在任何意义上都不是“线性”的。 - user684934

@bdares 身份函数在正确优化后根本不需要任何时间，因为它什么也不做。 - Robin Green

@Robin：无限空间并不等同于无限初始化空间。如何在常数时间内初始化一个无限空间哈希表？我很确定Debanjan所说的无界空间是指您可以分配额外的数组等。难道不是众所周知，使用O(n^2)空间将需要O(n^2)时间吗？因此，我真的没有看到您在这里的任何可信度。 - user127.0.0.1

顺便提一句，在某些研究中，有一篇文章谈到了使用未初始化的无符号整数数组：http://eli.thegreenplace.net/2008/08/23/initializing-an-array-in-constant-time/。我相信这些被称为稀疏数组。因此，如果我们允许使用整数值作为指针或偏移量随机访问无限内存，并将其作为数组或查找表，那么我们可以轻松地获得O（n）的解决方案。虽然这似乎是在作弊。 - user127.0.0.1

Answer 2

有k对整数之和为k：{0，k}，{1，k-1}，...等。创建一个大小为k+1的布尔元素数组B。对于数组A的每个元素e，如果e <= k且B[e] == false，则将B[e]设置为true，如果B[k-e] == true，则发出一对{e，k-e}。需要稍微扩展以处理负整数。

- cbare

Answer 3

我脑海中想到了一个简单的算法：

• 创建一个位域(bitfield)，表示从0到k的数字，标记为B
• 对于A中的每个数字i
  • 设置B[i]
  • 如果B[k-i]已设置，则将(i，k-i)添加到输出中

现在有人提出，如果你需要输出两个数字3的实例（3,3），那么只需交换上述算法中最后两个语句的顺序即可。

此外，我相信这个算法有一个名称，或者至少有更好的算法，如果有人知道的话，我会感激评论。

- Dominik Grabiec

---

你的算法花费时间O(k*n)，其中k是目标数字。这比O(n)要糟糕得多，多得多。 - user684934

不，它是O(n)，其中n由A的长度确定。位域是常数时间查找O(1)，而不是您所考虑的线性时间查找O(n)。 - Dominik Grabiec

是的，你说得对。我误读了你的算法，并假设你正在读取B中的每个插槽。 - user684934

此算法需要O(k)空间，等效于建议的（Java）哈希集解决方案（在C++中，set是一棵树）。 - Timofey

我觉得你可能有些困惑，Tim。我不使用集合数据结构，而是使用大小为k的位域(bitfield)，因此对于0到k之间的每个数字，都使用1个比特(bit)。如果你想要严谨一些，它将使用O( ceil( k / 8 ) )字节。 - Dominik Grabiec

实现代码：http://ideone.com/jOOZX4 - puneet

Answer 4

http://codepad.org/QR9ptUwR

这将打印所有的配对。算法与 @bdares 上面所说的相同。

我使用了 stl maps，因为在 STL 中我们没有哈希表。

- Vink

---

std::map<>::insert(x) 的时间复杂度为 O(log N)，而 std::map<>::count(x) 的时间复杂度为 O(N)。那么你的算法不就是 O(N^2) 吗？ - Robᵩ

@Rob Adams，我猜在map中的count是O(logN)，因为它不保存具有相同键的多个元素。在multimap中的count是O(N)。我上面的算法是O(NlogN)。如果我们使用哈希映射而不是map，那么我们会得到O(N)算法。 - Vink

从C++11开始，我们有了一种新的容器类型：unordered_map。 - Chiffa

为什么不在这里发布代码呢？;-) - Timofey

Answer 5

可以将元素唯一性位的复杂度降低到这个程度，不需要O(n)。

- Tarzan.

---

你能给一些提示，你指的是什么吗？或者一个关于元素唯一性位和约简的定义链接？ - kap