arrays - 具有重复值的 2sum

Question

经典的 2sum 问题简单且众所周知:

你有一个未排序的数组，并给你一个值 S。找到数组中所有元素对加起来等于值 S。

而且一直有人说这可以通过在 O(N) 时间和空间复杂度或 O(NlogN) 时间和 O(1) 空间复杂度先排序然后左右移动，

好吧，这两个解决方案显然是正确的，但我猜不适用于以下数组:

{1,1,1,1,1,1,1,1}

是否可以在 O(N) 或 O(NlogN) 时间复杂度内打印此数组中加起来为 2 的所有对？

Answer 1

不，打印所有对(包括重复项)需要 O(N<sup>2</sup>) 。原因是因为输出大小是O(N<sup>2</sup>) ，因此运行时间不能小于该时间(因为打印输出中的每个元素需要一些恒定的时间，因此简单地打印输出将花费 CN<sup>2</sup> = O(N<sup>2</sup>) 时间)。

如果所有元素都相同，例如{1,1,1,1,1} ，每个可能的对都会在输出中:

1. 1 1
2. 1   1
3. 1     1
4. 1       1
5.   1 1
6.   1   1
7.   1     1
8.     1 1
9.     1   1
10.      1 1

这是 N-1 + N-2 + ... + 2 + 1 (通过将每个元素与所有元素都放在右边)，即
N(N-1)/2 = O(N<sup>2</sup>) , 大于 O(N)或 O(N log N) .

但是，您应该能够简单地计算预期 O(N) 中的对数 通过:

• 创建 HashMap map将每个元素映射到它出现的频率。

• 遍历 HashMap 并为每个元素求和 x最多 S/2 (如果我们上升到 S，我们将包括 x 和 S-x 两次，如果 map 中不存在 map[x] == 0，则让 x):

  • map[x]*map[S-x]如果x != S-x (这是选择 x 和 S-x 的方式数)
  • map[x]*(map[x]-1)/2如果x == S-x (来自上面的 N(N-1)/2)。

当然你也可以在O(N)中打印不同的对 通过创建类似于上面的 HashMap 并循环遍历它，并且只输出 x和 S-x如果 map[S-x] 的值存在。