4

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

问题陈述：
给定一个未排序的整数数组 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) 时间复杂度。
所以我正在寻找任何可以进一步优化这个问题的方法或算法。

先感谢您！

4

3 回答 3

9

子集和问题是一个著名的 NP 完全问题。在这里，我假设您正在寻找任何一组数字来求和到目标（如果您实际上只寻找两个数字，那么有一个使用计数哈希表的五行解决方案，它在 O(n ） 时间）。

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

第二个是跟踪可以从列表的前缀中获得的总和。这是一种非常简单的方法，如果整数有界，效果很好。举例来说，如果输入是 n k 位整数，它的计算复杂度为 O(2 k n 2 )（伪多项式）：最大的和是 2 k n，所以表最多有 2 k n 2个条目。这是一种典型的动态规划方法，其中子问题为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
于 2013-02-01T18:26:43.300 回答
1

注意这个答案仍然提供信息，所以我保留它，但在 OP 的编辑之后它不太相关。

以下是我如何使用称为“哈希”的概念在O(n)运行时复杂性和空间复杂性中解决它。O(n)（其中 n 是数组的大小）

让我们拨打我想拨打的号码d

首先，我会创建某种HashTable（键值存储）。HashMaps 有O(1)插入、获取和包含。你可以在这里阅读它们

然后我会将每个对象放在哈希图中的单元格 d-object 中。在我检查下一个数字 x 之前，我会检查哈希映射是否包含单元格 x 处的值。如果是这样，我们就找到了我们的匹配项。

这是一些伪代码（我认为这比 C 代码更适合一般答案）

CheckIfTwoNumbersComplementTo(d,arr)
    map <-- new HashTable
    for each number x in Arr
        if(map contains a key for x)
            return true
        else
            add d-x to map if it is not already in map
    return false
于 2013-02-01T03:46:22.347 回答
0

如何对数组进行排序，并为每个元素计算目标值所需的对并搜索它？这将使排序的成本加上每个二进制搜索。

于 2013-02-01T03:52:09.547 回答