algorithm - 有效地获得排序列表的排序总和

Question

你有一个数字升序列表，你能想到的最有效的算法是什么来获得该列表中每两个数字的总和的升序列表。结果列表中的重复项无关紧要，您可以删除它们或根据需要避免它们。

明确地说，我对算法很感兴趣。随意使用您喜欢的任何语言和范例发布代码。

Answer 1

截至 2018 年的编辑:您可能应该停止阅读本文。 (但我无法删除它，因为它已被接受。)

如果你这样写出总和:

1 4  5  6  8  9
---------------
2 5  6  7  9 10
  8  9 10 12 13
    10 11 13 14
       12 14 15
          16 17
             18

您会注意到，由于 M[i,j] <= M[i,j+1] 且 M[i,j] <= M[i+1,j]，因此您只需要检查左上“角”并选择最低的一个。

例如

• 只有1个左上角，挑2个
• 只有1个，选5个
• 6或8，选6
• 7个或8个，选7个
• 9或8，选8
• 9 或 9，两个都选 :)
• 10 或 10 或 10，全选
• 12 或 11，选 11
• 12 或 12，两者都选
• 13 或 13，两者都选
• 14 或 14，两者都选
• 15 或 16，选 15
• 只有1个，选16个
• 只有1个，挑17个
• 只有1个，挑18个

当然，当您有很多的左上角时，这个解决方案就会发生变化。

我很确定这个问题是 Ω(n²)，因为您必须计算每个 M[i,j] 的总和——除非有人有更好的求和算法:)