设A是一个由n 个正整数组成的数组。
我怎样才能找到A 的一些索引k使得：
left = A[0] + A[1] + ... + A[k]
right = A[k+1] + A[k+2] + ... + A[n]
有最小的绝对差（即abs(left - right)最小）？
由于这种差异的绝对函数是抛物线的（减少到最小差异然后增加，如U），我听说三元搜索用于在这样的函数中查找值（抛物线），但我不知道如何实现它，因为我在互联网上进行了搜索，但没有发现三元搜索在抛物线函数上的用途。
编辑：假设我的所有区间总和都在 O(1) 中，并且我需要比 O(n) 更快的东西，否则我不需要三元搜索..
让left(k)表示数组中值的总和，从A[0]到A[k]。证明是微不足道的：
left(k+1)=left(k)+A[k+1]
如果您已经计算left了给定的 for k，那么leftfork+1是通过将下一个元素添加到 来计算的left。
换句话说：
如果您遍历数组，从元素 #0 到元素 #n-1（其中n是数组的大小），您left只需将数组中的下一个元素添加到left.
这似乎是显而易见的和不言而喻的，但它有助于正式说明这一点，以便该过程的下一步变得同样明显。
以同样的方式，给定right(k)表示数组中从元素 #k 开始直到数组中最后一个元素的值的总和，您还可以证明以下内容：
right(k+1)=right(k)-A[k]
因此，您可以通过从数组中所有值的总和 as和as开始，找到和k之间的最小差异（我使用的符号与您的问题使用的符号略有不同，因为我的符号更方便） ，然后然后， computing继续从头到尾迭代数组，在运行中计算这两个和每一步，并计算左值和右值之间的差异。找到差异最小的地方变得微不足道。left(k)right(k+1)right(0)A[0]left(0)right(1)leftright
我想不出任何其他方法来做到这一点，不到O(n)：
1) 计算数组中所有值的总和，初始值为right(0)O(n)。
2) 右边的迭代当然是 O(n)。
我不相信对数二进制搜索在这里会起作用，因为值abs(left(k)-right(k))本身不会按排序顺序排列。
顺便说一句，使用这种方法，您还可以在数组也包含负值时找到最小差异。唯一的区别是，由于差异不再是抛物线，您只需遍历整个数组，并跟踪abs(left-right)最小的位置。
简单的方法：
A[0] + A[1] + ... + A[k]和A[k+1] + A[k+2] + ... + A[n]任何k<=n。k最小化abs(left - right)k<=nO(n)在空间和时间上。
编辑：可以O(n)使用增量方法计算所有总和。