我最近在一次采访中被问到这个问题,并且只能给出一个二次解决方案:
给定一个带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个元素.这怎么可能在线性时间？