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

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

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

这很容易在 n 平方时间内完成，但是 问题指定它可以在 n 时间内完成，具有 n 个存储空间 space。 谁能推荐一下一个解法？从我的角度来看，即使有额外的 space，你也必须沿着数组保持运行。您需要知道整个数组的值，然后才能选择最小的切割。

Answer 1

有两个运行和，一个从位置 0 开始，另一个从 N 开始。

从起始位置初始化总和。

比较两个和，如果第一个和小于等于则将第一个和的光标位置向上移动，否则将第二个和的光标位置向下移动。

请检查您是否没有到达另一个总和的光标位置。如果你有，退出循环，你得到你的总和，你可以减去它们以获得最小的差异。

如果不是，则将新位置的新值添加到适当的求和和循环中。

Answer 2

通过两次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

Finding the position to cut an array in half, such that the difference of the sums is minimal