我试图解决问题,其中给出了一个整数数组,我需要找到给定数组中所有可能的元素对的总和.例如,数组是1,2,3,4那么它应该给1 + 2 + 1 + 3 + 1 + 4 + 2 + 3 + 2 + 4 + 3 + 4 = 30
现在,我尝试了不同的东西,但我不能带任何复杂度小于O(n ^ 2)的算法.有没有人对复杂度小于O(n ^ 2)的算法有所了解
G. *_*ach 11
由于数组的每个元素都是精确n-1对,因此将它们全部相加并乘以n-1,这意味着这是O(n).
这实际上推广到需要所有k元素多重集合之和的情况.在这种情况下,数组的每个元素都出现在多个(n-1) choose (k-1)集合中,因此将它们全部加起来并乘以它.二项式系数的计算在某些时候可能会变得有点多,但绝对可以枚举所有k元素多重集合并将它们相加.