arrays - 用列表中其他数字的总和替换数字而不用减法

Question

有人问我:

用剩余元素的总和替换列表中的每个数字，列表未排序。
因此，假设我们有一个数字列表，如 {2, 7, 1, 3, 8}，现在我们要用其余元素的总和替换每个元素。输出应该是:

    {(7 + 1 + 3 + 8), (2 + 1 + 3 + 8), (2 + 7 + 3 + 8), (2 + 7 + 1 + 8), (2 + 7 + 1 + 3)}
==  {19, 14, 20, 18, 13}

我回答了一个明显的解决方案:
首先计算所有数字的 sum，然后从 sum 中减去每个元素。所以对于上面的列表 sum 是 2 + 7 + 1 + 3 + 8 = 21，那么输出如下:

    {sum - 2, sum - 7, sum - 1, sum - 3, sum - 8}
    {21 - 2, 21 - 7, 21 - 1, 21 - 3, 21 - 8}
==  {19, 14, 20, 18, 13}

它只需要列表的两次迭代。

然后面试官问我:现在不做减法吗？我无法回答:(

是否有其他解决方案？有人可以分享任何其他技巧吗？可能有更好的技巧吗？

让额外的内存空间可以使用(我试了几分钟后才问，即使那样我也无法回答)。

Answer 1

一种可能是计算数组的前缀和后缀之和，然后组合适当的条目。这仍然是 O(n)，但需要更多的内存空间，所以我认为你原来的方法更好。

换句话说，从 {2, 7, 1, 3, 8} 计算 {2, 2+7, 2+7+1, 2+7+1+3, 2+7+1+3+8 } 和 {2+7+1+3+8, 7+1+3+8, 1+3+8, 3+8, 8} 然后添加适当的条目。