arrays - 查找数组中的最大值，即其他 3 个值的总和

Question

给定一个非常大的整数数组，我需要找到 a4 的最大值，这样:

a4 = a1 + a2 + a3

其中 ai 是数组中的所有值。

我该怎么做？

注意:使用 4 个 for 循环不是理想的解决方案。

Answer 1

有一个简单的(预期的)O(n^2) 解决方案:

1. 遍历所有数组元素对 (a, b) 并将它们的总和存储在哈希表中。
2. 遍历所有候选对 (a4, a1) 并检查 a4 - a1 是否在表中。所有有效 a4 的最大值是解决方案。当然你应该从大到小处理a4，但这不影响渐近。

如果您想避免多次使用一个元素，您需要在哈希表中存储一些额外的信息，以便您可以快速过滤掉与 a1 或 a4 冲突的对。

如果数组中的整数是有界的 (max - min <= C)，知道可以使用离散傅里叶变换(可使用 FFT 求解)实现 O(n + C log C) 可能会很有用。