algorithm - 给定一个最多包含 10 000 个不同自然数的向量，找到 4 个数 (a, b, c, d) 使得 a + b + c = d

Question

我通过遵循一个简单但不是最优的算法解决了这个问题。我按降序对向量进行排序，然后从最大值到最小值减去数字，看看是否得到 a + b + c = d。 请注意，我没有在任何地方使用元素是自然的、不同的和最多 10 000 个这一事实。我想这些细节是关键。 这里有没有人对解决此问题的最佳方法有任何暗示？

提前致谢!

稍后编辑: 我的想法是这样的:

'<<quicksort in descending order>>'

for i:=0 to count { // after sorting, loop through the array
    int d := v[i];
    for j:=i+1 to count {
        int dif1 := d - v[j];
        int a := v[j];

       for k:=j+1 to count {
           if (v[k] > dif1)
              continue;
           int dif2 := dif1 - v[k];
         b := v[k];

    for l:=k+1 to count {
 if (dif2 = v[l]) {
    c := dif2; 
     return {a, b, c, d}
 }
           }
        }
    }
}

你怎么看？(抱歉缩进不好)

Answer 1

O(n² log n) 中的解决方案:

计算所有可能的和与差的集合:

{a_i+a_j: 1 <= i,j <= n}

{a_i-a_j: 1 <= i,j <= n}

(将它们存储在平衡二叉搜索树中)并检查它们是否具有共同元素。如果是，则存在 i,j,k,l 使得 a_i + a_j = a_k - a_l，即a_i+a_j+a_l=a_k。

O(a_n log a_n) 中的解，其中 a_n 是向量中的最大数:

计算多项式

(x^a₁+x^a₂ + ... + x^a<子>n)³

你可以使用 Fast Fourier Transform 在 O(a_n log a_n) 中完成(首先计算平方，然后计算三次方；参见 here 了解说明)。观察乘法后系数 x^b_i 由乘法 x^a_i * x^{a 形成_j} * x^a_k= x^{a_i+a_j +a_k} 对于一些 i,j,k。检查生成的多项式中是否有幂 x^a_l。

不幸的是，这允许一些 i,j,k 被使用两次。减去 3(x^2a₁+...+x^2a_n)*(x^{a ₁}+...+x^a_n) - 2(x^3a₁+...+x^3a_n) 将删除那些 x^{a_i+a_j +a_k}。