algorithm - n个数字的成对和(不增加顺序)

我在编程中看到这个问题interview blog.
如果以非递减顺序给出n个数的成对和，则标识单个数。如果总和损坏，则打印-1。
例子：

i/p: 4 5 7 10 12 13

o/p: 1 3 4 9

一个暗示就足够了。

最佳答案

设B为成对和的列表，设B[0] <= B[1] <= ... <= B[m-1]为我们试图找到的原始数字列表，设A，其中A[0] < A[1] < ... < A[n-1]。
给定m = n(n-1)/2，在多项式时间内计算A[0]。
从最小元素到最大元素。假设我们已经知道A。然后，由于A是A[0]中最小的元素，因此它只能作为B[0]出现。同样，B必须等于A[0] + A[1]。因此，如果我们知道B[1]，我们就可以计算A[0] + A[2]和A[0]。
然而，在那之后，这种模式就崩溃了。A[1]可以是A[2]或B[2]，如果没有先验知识，我们无法知道它是哪一个。但是，如果我们知道A[0] + A[3]，我们可以按照上述方法计算A[1] + A[2]和A[0]，然后从A[1]中删除A[2]。下一个最小的元素保证是A[1] + A[2]，这允许我们找到B。继续这样，我们可以找到所有A[0] + A[3]而无需回溯。算法如下：

for i from 1 to n-1 {
    // REMOVE SEEN SUMS FROM B
    for j from 0 to i-2 {
        remove A[j]+A[i-1] from B
    }
    // SOLVE FOR NEXT TERM
    A[i] = B[0] - A[0]
}
return A

下面是您的示例中的工作原理，如果我们知道A[3]：

start
    B = [4,5,7,10,12,13]
    A[0] = 1

i=1:
    B = [4,5,7,10,12,13]
    A[1] = 4-1 = 3

i=2:
    Remove 1+3 from B
    B = [5,7,10,12,13]
    A[2] = 5-1 = 4

i=3:
    Remove 1+4 and 3+4 from B
    B = [10,12,13]
    A[3] = 10-1 = 9

end
    Remove 1+9 and 3+9 and 4+9 from B
    B = []
    A = [1,3,4,9]

所以这一切都归结为知道A，从中我们可以计算出B = [4,5,7,10,12,13]的其余部分。
在多项式时间内计算
我们现在可以简单地尝试A[0]=1的所有可能性。因为我们知道A[0]，所以我们知道A必须是A[0]和A[0]之间的整数。我们也知道

B[0] = A[0] + A[1]
B[1] = A[0] + A[2]

此外，还有一些指数B[0] = A[0] + A[1]和A[0]这样

B[i] = A[1] + A[2]

为什么？因为只有可能小于0的条目是B[0]/2 - 1形式的，并且最多有这样的表达式。因此我们也知道

A[0] = (B[0]+B[1] - B[i])/2

对于某些i。这加上2 <= i <= n-1介于A[1]+A[2]和A[0] + A[j]之间，使得n-1测试的可能性很小。
例如，有两种可能性2 <= i <= n-1：A[0]或0。如果我们使用B[0]/2-1尝试算法，会发生以下情况：

start
    B = [4,5,7,10,12,13]
    A[0] = 0

i=1:
    B = [4,5,7,10,12,13]
    A[1] = 4-0 = 4

i=2:
    Remove 0+4 from B
    B = [5,7,10,12,13]
    A[2] = 5-0 = 5

i=3:
    Remove 0+5 and 4+5 from B
    B = !!! PROBLEM, THERE IS NO 9 IN B!

end

关于algorithm - n个数字的成对和(不增加顺序)，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/8566534/