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

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太大时递减上部索引）

产生的复杂性是二次的

Answer 2

出于兴趣，我们可以使用快速傅里叶变换在O(n log n + m log m)时间解决这个问题，其中m是范围。

首先对输入进行排序。现在考虑通过从另一个中减去一个差异前缀和，可以实现数字之间可达到的每个距离。例如：

input:            1 3 7
diff-prefix-sums:  2 6
difference between 7 and 3 is 6 - 2

现在让我们将等式（最右边的前缀和）添加到等式的每一边：

ps[r] - ps[l]       = D
ps[r] + (T - ps[l]) = D + T

我们列出差异：

1 3 7
 2 4

和前缀总和：

p     => 0 2 6
T - p => 6 4 0  // 6-0, 6-2, 6-6

我们需要有效地确定所有不同可实现差异的计数。这类似于将多项式与系数[1, 0, 0, 0, 1, 0, 1]乘以多项式与系数[1, 0, 1, 0, 0, 0, 0]（我们不需要第二组中的零系数，因为它只生成小于或等于T的度数），我们可以在m log m时间完成，其中m是度，具有快速傅里叶变换。

结果系数为：

  1 0 0 0 1 0 1
* 
  1 0 1 0 0 0 0
=> 
  x^6 + x^2 + 1
*
  x^6 + x^4

= x^12 + x^10 + x^8 + 2x^6 + x^4 

=> 1 0 1 0 1 0 1 0 1 0 0 0 0

我们丢弃低于或等于T的度数，并显示我们的有序结果：

1 * 12 = 1 * (T + 6) => 1 diffs of 6
1 * 10 = 1 * (T + 4) => 1 diffs of 4
1 *  8 = 1 * (T + 2) => 1 diffs of 2

如果任何系数，它们的负数或T都在我们的数组元素集中，我们就匹配了。