面试：sumPairs(array) 在 O(n) 时间内输出所有求和对的总和
Interview: sumPairs(array) output the sum of all summed pairs in O(n) time
我最近在面试中被问到这个问题，只能给出二次解：
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
我的方法是生成所有 2 元组 NC2（N 选择 2），并保持它们总和的 运行。但是，我不确定如何在线性时间内完成它。据我所知，对于大小为 n 的列表，存在 n*(n-1)/2 个元素。在线性时间内这怎么可能？
您不需要生成元组，您只需将每个元素添加 (n-1) 次即可：
sum = 0
for each x:
sum = sum + x*(n-1)
这是基于每个元素与其他元素恰好相加一次，因此总共相加 n-1 次。
我最近在面试中被问到这个问题，只能给出二次解：
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
我的方法是生成所有 2 元组 NC2（N 选择 2），并保持它们总和的 运行。但是，我不确定如何在线性时间内完成它。据我所知，对于大小为 n 的列表，存在 n*(n-1)/2 个元素。在线性时间内这怎么可能？
您不需要生成元组，您只需将每个元素添加 (n-1) 次即可：
sum = 0
for each x:
sum = sum + x*(n-1)
这是基于每个元素与其他元素恰好相加一次，因此总共相加 n-1 次。