将数字替换为列表中其他数字的总和而不减法

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}然后添加适当的条目.