2sum具有重复值 [英] 2sum with duplicate values

问题描述

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

The classic 2sum question is simple and well-known:

您有一个未排序的数组，并且被赋予了值S。在

You have an unsorted array, and you are given a value S. Find all pairs of elements in the array that add up to value S.

一直有人说，可以通过在 O（N）<中使用HashTable来解决此问题。 / code>时间&空间复杂度或 O（NlogN）时间和 O（1）空间复杂度，方法是先对其进行排序然后从左移没错，

And it's always been said that this can be solved with the use of HashTable in O(N) time & space complexity or O(NlogN) time and O(1) space complexity by first sorting it and then moving from left and right,

这两个解决方案显然是正确的，但我猜不是针对以下数组：

well these two solution are obviously correct BUT I guess not for the following array :

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

是否可以打印全部对在此数组中以 O（N）或 O（NlogN）时间复杂度加起来最多为2？ p>

Is it possible to print ALL pairs which add up to 2 in this array in O(N) or O(NlogN) time complexity ?

推荐答案

不，打印所有对（包括重复项）需要 O（N 2 ） 。原因是因为输出大小为 O（N 2 ），因此运行时间不能小于该时间（因为它需要一定的数量时间来打印输出中的每个元素，因此仅打印输出将花费 CN 2 = O（N 2 ）时间）。

No, printing out all pairs (including duplicates) takes O(N2). The reason is because the output size is O(N2), thus the running time cannot be less than that (since it takes some constant amount of time to print each element in the output, thus to simply print the output would take CN2 = O(N2) time).

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

If all the elements are the same, e.g. {1,1,1,1,1}, every possible pair would be in the output:

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 2 ），大于 O（N）或 O（N log N）。

This is N-1 + N-2 + ... + 2 + 1 (by taking each element with all elements to the right), which is
N(N-1)/2 = O(N2), which is more than O(N) or O(N log N).

但是，您应该能够通过以下方式简单地计算期望的 O（N） 中的货币对：

However, you should be able to simply count the pairs in expected O(N) by:

• 创建一个哈希映射 map 将每个元素映射到其出现频率。

• Creating a hash-map map mapping each element to the count of how often it appears.

遍历哈希图并求和，对于每个元素 x 至 S / 2 （如果我们升至 S ，我们将包括 x 和 Sx 两次，如果 x 不这样做，则让 map [x] == 0

Looping through the hash-map and summing, for each element x up to S/2 (if we go up to S we'll include the pair x and S-x twice, let map[x] == 0 if x doesn't exist in the map):

• map [x] * map [S -x] 如果 x！= Sx （这是选择 x 和 Sx ）


• map [x] *（map [x] -1）/ 2 如果 x == Sx （来自上面的 N（N-1）/ 2 ）。

• map[x]*map[S-x] if x != S-x (which is the number of ways to pick x and S-x)
• map[x]*(map[x]-1)/2 if x == S-x (from N(N-1)/2 above).

当然，您也可以在 O（N） ，方法是创建类似于上面的哈希图并循环遍历，仅输出 x 和 Sx 值，如果 map [Sx] 存在。

Of course you can also print the distinct pairs in O(N) by creating a hash-map similar to the above and looping through it, and only outputting x and S-x the value if map[S-x] exists.

这篇关于2sum具有重复值的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！