检查2个数组是否与I相加

Question

我看到一个面试问题如下:给出一个未排序的整数数组A和一个整数I,找出A的任何两个成员是否加起来我.

任何线索？

时间复杂度应该更少

Answer 1

将元素插入哈希表.

插入时x,检查是否I-x已存在.O(n)预计时间.

否则,将数组升序排序(从索引0到n-1).有两个指针,一个是最大值,一个是最小值(分别称为M和m).

If a[M] + a[m] > I then M-- 
If a[M] + a[m] < I then m++
If a[M] + a[m] == I you have found it
If m > M, no such numbers exist.

Answer 2

如果您具有整数所在的范围,则可以使用计数排序式解决方案,在该解决方案中扫描数组并计算数组.你有整数

input = [0,1,5,2,6,4,2]

你创建一个像这样的数组:

count = int[7]

其中(在Java中,C#等)适用于计算0到6之间的整数.

foreach integer in input
    count[i] = count[i] + 1

这将为您提供阵列[1,1,2,0,1,1,1].现在,你可以扫描在这个阵列(的一半),并检查是否有整数加起来到i喜欢

for j = 0 to count.length - 1
    if count[j] != 0 and count[i - j] != 0 then // Check for array out-of-bounds here
         WUHUU! the integers j and i - j adds up

总的来说,这个算法给出了O(n + k)n在长度为n的输入上扫描的位置,k是在长度为k的计数数组上的扫描(0和k-1之间的整数).这意味着如果n > k那时你有一个有保障的O(n)解决方案.

Answer 3

1. 对数组进行排序
2. 每个元素X中A,执行对二进制搜索I-X.如果I-X是A,我们有一个解决方案.

这是O(nlogn).

如果A包含给定(足够小)范围内的整数,我们可以使用技巧来实现O(n):

1. 我们有一个数组V.对于每一个元素X中A,我们增加V[X].
2. 当我们增加V[X]我们还要检查是否V[I-X]是>0.如果是,我们有一个解决方案.

Answer 4

例如,循环并添加可能的数字来设置或散列,如果找到,只需返回它.

>>> A = [11,3,2,9,12,15]
>>> I = 14
>>> S = set()
>>> for x in A:
...     if x in S:
...         print I-x, x
...     S.add(I-x)
...
11 3
2 12
>>>