arrays - 找到将数组切成两半的位置，使得总和的差异最小

Question

我正在做一些编程练习题来准备面试。

其中一个问题如下:您试图找到将数组切成两半的位置，以使每一半之和之间的差异最小化。可以实现的最小差异是多少？

所以

A[0] = 3
  A[1] = 1
  A[2] = 2
  A[3] = 4
  A[4] = 3

我们可以把这个磁带分成四个地方:

P = 1, difference = |3 − 10| = 7 
P = 2, difference = |4 − 9| = 5 
P = 3, difference = |6 − 7| = 1 
P = 4, difference = |10 − 3| = 7 

所以我们会返回 1，因为这是最小的差异。

这很容易在 n 平方时间内完成，但是问题指定它可以在 n 时间内完成，具有 n 个存储空间。任何人都可以推荐一个解决方案吗？我以任何方式看待它，即使有额外的空间，你也必须继续沿着阵列运行。您需要知道整个数组的值，然后才能选择最小的切割。

Answer 1

通过两次 O(n) 遍可以找到中间的切割位置。考虑你原来的问题:

A[0] = 3
A[1] = 1
A[2] = 2
A[3] = 4
A[4] = 3

迭代这个值数组并将增量总和记录在一个名为 sums 的新数组中:

sums[0] = 3
sums[1] = 4
sums[2] = 6
sums[3] = 10
sums[4] = 13

在这次迭代之后，您还知道总和是多少，在本例中是13。现在您需要做的就是遍历sums 数组并选择最接近 一半 总和的值。在这种情况下，sums[2] = 6 符合要求，因此您可以在第三个位置进行削减。

sums[0] = 3
sums[1] = 4
sums[2] = 6
-----------      <-- make the cut here
sums[3] = 10
sums[4] = 13