如何将两个等长数组元素配对相加，使结果数组分布最均匀？

你的方案是最优解 #

你提出的「将数组a升序排序、数组b降序排序后对应位置相加」的策略，确实是解决这个问题的最优方案。

核心逻辑很直接：要让所有配对和的最大值与最小值差值最小，就得避免出现「大值+大值」「小值+小值」的极端组合。通过大值配小值的方式，能最大程度拉平每一组的和，从数学上可以证明，这种配对方式的极差是所有可能配对中最小的。

高效的Python实现 #

Python内置的Timsort排序算法效率极高，基于这个思路的实现代码简洁且性能最优（时间复杂度为O(n log n)，这是此类问题的理论最优复杂度）：

def minimize_sum_range(a, b):
    # 对a升序排序，b降序排序
    a_sorted = sorted(a)
    b_sorted = sorted(b, reverse=True)
    # 对应位置相加得到数组c
    c = [x + y for x, y in zip(a_sorted, b_sorted)]
    # 返回极差和结果数组c
    return max(c) - min(c), c

如果想节省空间，可以直接对原数组进行原地排序（注意会修改原数组）：

def minimize_sum_range_inplace(a, b):
    a.sort()
    b.sort(reverse=True)
    c = [x + y for x, y in zip(a, b)]
    return max(c) - min(c), c

简单验证示例 #

比如取a = [1, 3, 5, 7]，b = [2, 4, 6, 8]：

• 按方案配对得到的c为[9, 9, 9, 9]，极差为0，完全均匀。
• 如果采用a、b都升序配对，得到的c为[3, 7, 11, 15]，极差达到12，差距非常明显。

内容的提问来源于stack exchange，提问作者Aline A