采访:sumPairs(数组)输出O(n)时间内所有求和对的总和

Question

我最近在一次采访中被问到这个问题,并且只能给出一个二次解决方案:

给定一个带n个数字的数组.给出一个算法(sumPairs)来找到所有数字对之和的累积和.该算法应为O(n)时间.

例如:sumPairs([1,2,3,4]):

所有对都是:(1 + 2)+(1 + 3)+(1 + 4)+(2 + 3)+(2 + 4)+(3 + 4)

所有求和对的总和:(1 + 2)+(1 + 3)+(1 + 4)+(2 + 3)+(2 + 4)+(3 + 4)= 30

我的方法是生成所有2元组,NC2(N选择2),并保持其总和的总和.但是,我不确定如何在线性时间内完成它.据我所知,对于大小为n的列表,存在n*(n-1)/ 2个元素.这怎么可能在线性时间？

Answer 1

您不需要生成tupples,只需添加每个元素(n-1)次:

sum = 0
for each x:
  sum = sum + x*(n-1)

这是基于这样一个事实,即每个元素与其他元素恰好相加一次,因此总共添加n-1次.