algorithm - 没有洗牌的分区总和

Question

在一个面试题中，我得到了一个稍微不同版本的分区和问题:给你一个数组，找到分区索引，使得左数组的和等于右数组的和。在这里，我们不能打乱元素以形成分区

例如:[5,1,8,2,2,9,1]

5 + 1 + 8 = 2 + 2 + 9 + 1 = 14

9 + 5 = 8 + 2 + 2 + 1 + 1 但这不是这个问题的有效答案，因为我们不能打乱元素。

我说我们可以做一个左和右和，左数组和右数组。从 leftsum = 5(第一个元素的总和)和 right sum = 23(所有其他元素的总和)开始。然后遍历右数组并继续检查左和=右和。如果不是，则减去右数组中的第一个元素并将其添加到左数组中。在这里，它是左和 = 5 + 1 = 6，右和 = 23 - 1 = 22。

同样:左和 = 6 + 8 = 14，右和 = 22 - 8 = 14由于 leftsum = rightsum，我们将分区索引返回为 2

如果我们到达正确数组的末尾，则意味着该分区不存在，我们返回无效。

尽管面试官说答案似乎是正确的，但他似乎对我的解决方案并不满意。这个问题有更有效的解决方案吗？

Answer 1

你的算法的时间/空间复杂度是最优的，但是:

• 此类问题的部分目的是了解您还问了哪些问题。在这种情况下，您可以询问(如果尚未指定)是否:

  • 数字都是整数，也可以出现小数
  • 数字全部为非负数，或出现负数

• 当您提到 left 和 right 数组时，您给人的印象是该解决方案处理 2 个单独的数组变量。此外，从 中减去 和添加到 数组可以加强您在更改两个不同数组的大小时分配和释放内存的想法。这效率不高，甚至可以解释为使用 O(n) 空间。

• 您的解决方案使用了两个总和，而它可以用一个总和来完成。

• 一个关键观察结果是，如果所有值的总和为 n，则分区的总和应为 n/2。如果您有一个分区具有该总和，那么显然另一个分区也具有该总和。此外，如果保证值是整数，n 应该是偶数。如果这很奇怪，您可以停止进一步寻找，因为没有解决方案。

所以有符号整数的算法可以这样表示:

sum = 0
for i = 0 to len(array)-1:
    sum = sum + array[i]
if sum % 2 == 1:
    return -1      # no solution
sum = sum / 2
for i = 0 to len(array)-1:
    if sum == 0:
        return i   # solution
    sum = sum - array[i]
return -1    # no solution

查看它在 repl.it 上运行

注意可以有多个解决方案(例如输入 [0,0,0,0] 或 [5,-1,1,-1,1,-1,1,-1 ,1,5]`).该算法将只返回它找到的第一个。

如果假定值始终为非负数，那么您可以使用此算法，它可以运行得更快一些(但时间复杂度不会不同)，因为它只访问数组值一次:

sum = 0
left = 0
right = len(array) - 1
while left <= right:
    if sum < 0:
        sum = sum + array[left]
        left = left + 1
    else:
        sum = sum - array[right]
        right = right - 1
if sum = 0:
    return left  # solution
return -1      # no solution

查看它在 repl.it 上运行