一个数组中所有可能配对元素的和

Question

我正在尝试解决一个问题，给定一个整数数组，我需要找到所有可能的元素对之和。例如，数组为1,2,3,4，则结果应该是1+2 + 1+3 + 1+4 + 2+3 + 2+4 + 3+4 = 30。

我尝试了不同的方法，但是没有想出复杂度低于O(n^2)的算法。请问是否有任何关于复杂度低于O(n^2)的算法？

- rovy

---

我不知道这个问题与编程有什么关系，请尝试访问math.stackexchange.com。 - Chiel

@Chiel 这是一个编程问题，我正在编写Java程序，但我认为必须有一些算法可以在少于O(n^2)的时间内解决它。 - rovy

对于一个不是O(n^2)的解决方案，需要额外的限制条件（例如数组中的元素是连续整数等）吗？ - Steven Evers

@SnOrfus.. 不，没有其他限制..看看G. Bach的答案，它完美地给出了答案。 - rovy

Answer 1

自数组中的每个元素都恰好出现在 n-1 对中，因此将它们全部相加并乘以 n-1，即为 O(n)。

---

实际上，这适用于需要求所有 k 元多重集合和的情况。在这种情况下，数组中的每个元素都恰好出现在 (n-1) 选择 (k-1) 个多重集中，因此将它们全部相加并乘以该值。计算二项式系数可能会有点困难，但绝对比枚举所有 k 元多重集并将它们相加要好。

- G. Bach

---

@G. Bach非常感谢您的回复。这正是我想要的。 - rovy

Answer 2

除非您对数组中的值有所了解，否则我看不到任何不是O(n^2)的方法可以做到这一点。

N个物品取2个的组合数为：

N           C
10          45
100       4950
1000    499500

正如您所看到的，组合数量约为（N^2）/2，因此我不认为在没有额外信息的情况下您能做得更好。

- Wayne Tanner

Answer 3

在C++中有一个叫做next_permutation()的函数，它可以生成数组中下一个元素的“组合”。因此，您可以像这样做：

int A=[1,2,3,4,5];
while(next_permutation(A,A+5)) //NOTE: A is pointer to first element of array A
{
    // do something
}

如果你理解了这个想法，你应该能够为你的问题定制代码。

- Dominik