arrays - 如何改进算法来检查数组中是否有一个元素等于数组中任何其他两个元素之间的差值？

Question

我知道这显然是一个简单的问题。但是我找不到更好的方法来提高效率。这就是我正在尝试的。这很天真，但我仍然无法正确理解。

1. 对数组进行排序。 (分而治之)

2. a) 一次选择一个元素 b) 遍历数组的所有剩余元素(成对)得到 它们之间的差异以匹配所选元素。

3. 重复步骤 2，直到至少找到所有元素。
4. 存储所有符合条件的元素。
5. 打印存储的元素。

Answer 1

条件 A[i] - A[j] = A[k] 等于 A[i] = A[j] + A[k],所以我们可以求和。

对数组进行排序。

对于每个元素搜索，如果它是两个其他元素的总和，使用 two pointers approach (sum太小自增下标，sum过大自减上标)

由此产生的复杂度是二次的