给定最大10 000个自然和不同数字的向量,找到4个数字(a,b,c,d),使a + b + c = d

Question

我通过遵循一个简单但非最优的算法解决了这个问题.我按降序对矢量进行了排序,之后从max到min减去了数字,看是否得到a + b + c = d.请注意,我没有在任何地方使用过这样一个事实:元素是自然的,不同的,最多只有10000个.我想这些细节是关键.这里有没有人提示解决这个问题的最佳方法？

先感谢您!

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

'<<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,即_i + a _j + a _l = a _k.

O(a _n log a _n)中的解,其中_n是向量中的最大数字:

计算多项式

(x ^{a ₁} + x ^{a ₂} + ... + x ^{a _n})³

你可以使用快速傅立叶变换在O(a _n log a _n)中进行(第一个计算平方,然后是第三个幂;参见此处的描述).观察到在乘法之后,系数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}.