以下是“亚马逊”向我提出的面试问题。我还没有想出一个优化的解决方案。
问题陈述:
给定一个未排序的整数数组 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) 时间复杂度 。
所以我正在寻找任何可以更多地优化这个问题的方法或算法。
先感谢您!
最佳答案
子集和问题是众所周知的 NP 完全问题。在这里，我将假设您正在寻找与目标相加的任何一组数字(如果您实际上只寻找两个数字，则有一个使用计数哈希表的五行解决方案，该哈希表在 O(n ) 时间)。
有两种基本方法。第一个只是测试每个可能的子序列。正如您已经观察到的，这需要 O(2n) 时间(指数)，如果 n 为 1000，这将是棘手的。
第二个是跟踪可以从列表的前缀中获得的总和。这是一种非常简单的方法，如果整数有界，则效果很好。举例来说，如果输入是n个k位整数，它的计算复杂度为O(2kn2)(伪多项式):求和最大可以得到2kn，所以该表最多有2kn2个条目。这是典型的动态规划方法，其中子问题是 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
关于c - 通过执行整数加法在未排序的整数数组中找到目标值，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/14639346/