经典2sum问题是简单的和众所周知的：
你有一个排序的数组，并且您将得到一个数值S.找到所有对，加起来值S的数组中的元素
它总是有人说，这可以在使用哈希表来解决O(N)的时间和空间复杂度还是O(NlogN)的时间和O(1)空间复杂度，首先分拣，然后由左，右移动，
以及这两个解决方案显然是正确的，但我想不会对下面的数组：
{1,1,1,1,1,1,1,1}
是否有可能打印所有对其中至多这个阵列中添加2 O(N)或O(NlogN)时间复杂度？
Answer 1:
否， 打印出的全部组（包括重复）取O(N 2 ) 其原因是因为该输出大小是O(N 2 )因此，在运行时间不能比更小（因为它需要一些恒定量的时间来打印每个元件在输出中，从而简单地打印输出将采取CN 2 = O(N 2 )的时间）。
如果所有的元件是相同的，例如{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 2 )这比更O(N)或O(N log N)
但是，你应该能够简单地计算预期的对O(N)的：
创建一个哈希地图
map映射每个元素的它出现的频率计数。通过散列映射循环和求和，每个元素
x高达S/2（如果我们上去S我们将包括一对x和Sx两次，让map[x] == 0，如果x不存在在地图）：-
map[x]*map[Sx]如果x != Sx（其方式挑数x和Sx） -
map[x]*(map[x]-1)/2，如果x == Sx（从N(N-1)/2以上）。
-
当然也可以打印在不同的对O(N)通过创建一个散列映射类似于上面，并通过它循环，并仅输出x和Sx的值，如果map[Sx]存在。
Answer 2:
显示或存储的结果是O（N 2）only.The最坏的情况下由您所强调清楚地具有N 2对和将它们写入到屏幕上或将它们存储到结果阵列显然需要至少那么多time.In短， 你是对的！
Answer 3:
没有
在O（nlogn）可以预先计算它们使用排序，而是打印出来，你可能需要超过O（nlogn）。在最坏的情况下它可以是O（N ^ 2）。 让我们修改算法来找出所有重复对。
举个例子：
a[ ]={ 2 , 4 , 3 , 2 , 9 , 3 , 3 } and sum =6
排序后：
a[ ] = { 2 , 2 , 3 , 3 , 3 , 4 , 9 }
假设你发现对{2,4}，现在你必须要找到的2和4的数量和它们相乘得到没有重复pairs.Here 2发生2次和1出现1个times.Hence {2,1}将出现2 * 1 = 2 output.Now倍考虑当两个数字是相同的特例然后计数没有发生和SQ它们。这里{3,3}总和至6在阵列发生3是3.Hence {3,3}将出现在输出端9倍。
在您的数组{1,1,1,1,1}只对{1,1}将总结为2和1计数5.hence有要5 ^ 2 =25对{1,1}中输出。
文章来源: 2sum with duplicate values
