arrays - 采访 : sumPairs(array) output the sum of all summed pairs in O(n) time

Question

我最近在面试中被问到这个问题，只能给出二次解:

Given an array with n numbers. Give an algorithm (sumPairs) to find the cumulative sum of the sum of all pairs of numbers. The algorithm should be O(n) time.

For example: sumPairs([1,2,3,4]):

All pairs are: (1+2) + (1+3) + (1+4) + (2+3) + (2+4) + (3+4)

Sum of all summed pairs: (1+2) + (1+3) + (1+4) + (2+3) + (2+4) + (3+4) = 30

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

Answer 1

你不需要生成元组，你可以只添加每个元素 (n-1) 次:

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

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