通过执行整数的添加,在未排序的整数数组中查找目标值

Question

以下是"亚马逊"向我提出的面试问题.我还没有想出一个优化的解决方案.

问题陈述:
给出一个未排序的整数数组n.如果从该数组添加任何整数与目标值匹配,则返回'true',否则返回false.

注意:

   1)'n' could be 1000 or 10,000.
   2) Target value could be 'negative'
   3) It may be addition of any 'k' integers (not only two) , where k<=n.  

测试条件:

    i/p:- Array A[]= {6,7,3,0,12,-5,-6,100}
    Target =  8
    o/p:- TRUE        
As, 6+7+(-5)=8

如果我们尝试线性地或正常地执行它将花费O(2 ^ n)时间复杂度.
所以我正在寻找能够更好地优化这个问题的任何方法或算法.

先感谢您!

Answer 1

子集和问题是一个众所周知的NP完全问题.在这里,我将假设您正在寻找任何数字总和以达到目标(如果您实际上只查找两个数字,那么使用计数哈希表的五行解决方案在O(n)中运行) 时间).

有两种基本方法.第一个是测试每个可能的子序列.正如您已经观察到的那样,需要O(2 ⁿ)时间(指数),如果n为1000则这是难以处理的.

第二个是跟踪从列表的前缀可以获得的总和.这是一种非常简单的方法,如果整数有界,则效果很好.举例来说,如果输入是n个k位整数,则它具有计算复杂度O(2 ^k n ²)(伪多项式):总和可以得到的最大值是2 ^k n,因此该表最多具有2 ^k n ²个条目.这是一种典型的动态编程方法,其中子问题是T[s][k] = (A[1..k] has a subsequence summing to s),最终解决方案由下式给出T[target][n].

这是Python实现这个的解决方案:

def subset_sum(A, target):
    T = {0} # T[s][0] = (TRUE iff s == 0)
    for i in A:
        T |= {x + i for x in T}
    return target in T

例子:

>>> subset_sum([-5,6,7,1,0,12,5,-6,100], 13)
True
>>> subset_sum([95, -120, 22, 14491], 13)
False

额外奖励:如果你很好奇,这里是配对问题的解决方案.它在O(n)时间内运行并告诉您阵列是否有两个与目标相加的数字.

from collections import Counter
def pair_sum(A, t):
    C = Counter(A)
    for k,v in C.iteritems():
        if t == k+k and v > 1: return True # k is in the array twice
        elif t != k+k and t-k in C: return True
    return False

例子:

>>> pair_sum([3,3,3,4], 13)
False
>>> pair_sum([3,3,3,10], 13)
True
>>> pair_sum([7,7,2], 14)
True
>>> pair_sum([7,14,2], 14)
False