从4组求和为0的算法

Question

我有4个阵列A,B,C,D大小n.n最多为4000.每个数组的元素是30位(正/负)数字.我想知道方法的数量,A[i]+B[j]+C[k]+D[l] = 0可以在哪里形成0 <= i,j,k,l < n.

我推导出的最好的算法是O(n^2 lg n),有更快的算法吗？

Answer 1

好的，这是我的 O(n^2lg(n^2)) 算法 -

假设有四个数组A[]、B[]、C[]、D[]。我们想要找到 A[i]+B[j]+C[k]+D[l] = 0 的路数，其中 0 <= i,j,k,l < n。

因此，总结 A[] 和 B[] 的所有可能排列，并将它们放入另一个包含 n*n 个元素的数组 E[] 中。

int k=0;
for(i=0;i<n;i++)
{
    for(j=0;j<n;j++)
    {

        E[k++]=A[i]+B[j];


    }
}

上述代码的复杂度为O(n^2)。

对 C[] 和 D[] 执行相同的操作。

int l=0;

for(i=0;i<n;i++)
{
     for(j=0;j<n;j++)
     {

          AUX[l++]=C[i]+D[j];

     }
}

上述代码的复杂度为O(n^2)。

现在对AUX[]进行排序，以便您可以轻松找到AUX[]中唯一元素出现的次数。

AUX[] 的排序复杂度为 O(n^2 lg(n^2))。

现在声明一个结构-

struct myHash
{
  int value;
  int valueOccuredNumberOfTimes; 

}F[];

现在在结构 F[] 中放置 AUX[] 的唯一元素以及它们出现的次数。

其复杂度为O(n^2)

possibleQuardtupple=0;

现在，对于 E[] 的每一项，执行以下操作

for(i=0;i<k;i++)
 {

     x=E[i];

     find -x in structure F[] using binary search.
     if(found in j'th position)
     {
        possibleQuardtupple+=number of occurrences of -x in F[j];

     }      
 }

对于循环 i ，执行总共 n^2 次迭代，并且在每次迭代中进行二分搜索 lg(n^2) 比较。所以总体复杂度是 O(n^2 lg(n^2))。

可以到达的路数为 0 = possibleQuardtuple。

现在您可以使用 stl map/二分搜索。但是stl map速度慢，所以最好使用二分查找。

希望我的解释足够清楚理解。