鉴于4个阵列，发现具有零和四倍

Question

• 鉴于4个阵列可以包含正数和负数的数目。
• 找到所有可能的集合与来自每个阵列的一个号码（即，每个组将包含4个数字）的4个数字，使得总和是零。

Answer 1

阿德里安只是没有想到足够远:-)

遍历阵列1和2以及所有款项添加到地图。

现在从其他2个数组中找到所有组合，这些组合在地图上从数组1和2中获得的数字相加。它非常简单。让我知道你是否需要伪代码。

O（n^2）运行时间

Answer 2

强制的方法：注：我没有测试过这

public void setsOfZero(int[] one,int[] two,int[] three,int[] four) 
    { 
     List<IntegerSet> setsOfIntegers = new ArrayList<IntegerSet>(); 
     for(int i =0;i < one.length ; i++) 
     { 
      for(int k = 0; k < two.length; k++) 
      { 
       for(int j = 0; j<three.length; j++) 
       { 
        for(int l = 0;l< four.length; l++) 
        { 
         if((one[i]+ two[k] + three[j] + four[l])==0) 
         { 
          IntegerSet intSet = new IntegerSet(); 
          intSet.one = one[i]; 
          intSet.two = two[k]; 
          intSet.three = three[j]; 
          intSet.four = four[l]; 

          setsOfIntegers.add(intSet); 
         } 
        } 
       } 
      } 
     } 
    } 

IntegerSet类

public class IntegerSet{ 
    public int one =0; 
    public int two =0; 
    public int three =0; 
    public int four =0; 
} 

Answer 3

遍历数组1，所有的元素添加到地图。

从其他3个阵列

现在找到其表，其中从阵列1.拿到这是非常简单的地图添加到一个号的所有组合。让我知道你是否需要伪代码。 O（n^3）运行时间

更好的解决方案是将数组2和2进行组合并对它们进行求和。你可以把它推广到n个数组（其中n是偶数）。您正在构建一个树形结构，其中每个节点都是一个数组。叶子是最初给定的数组，然后是一级，另外还有2个数组（从叶子开始），依此类推。 nlogn runtime，其中n是数组的平均大小。 （每个元素@position我[在阵列]您建立一个树）

编辑： 刚一说明（由于历史原因）
我记得我曾经有过类似的问题。我所做的是仍然使用这种二叉树方法，但是我在树的每个阶段计算了组合。我把2个数组合并成一个大小为n^2的大数组。然后在下一个阶段新阵列的大小是n^4等等。当我剩下两个数组时，我映射了一个数组。然后只检查另一个数组中的元素是否在地图中。

Answer 4

如果你想找到所有的人，没有办法做到在O（N^4），因为可以有很多套。

如果你想不过算来，这可以在为O（n^2日志n）和O（N^2）空间由相遇中间人招解决。

我们称之为阵列A，B，C，D。我们创建了两个阵列X和Y

for a in A: 
    for b in B: 
     X.append(a + b) 

用于Y

同样的事情C和D.你排序X和Y（在为O（n^2 log n））。然后你这样做：

i = 0 
j = size(Y) - 1 
count = 0 
while i < size(X) and j >= 0: 
    if X[i] + Y[j] == 0: 
     ii = 1 
     jj = 1 
     while X[i] == X[i + 1]: 
      ii++ 
      i++ 
     while Y[j] == Y[j - 1]: 
      jj++ 
      j-- 
     count += ii * jj 
    if X[i] + Y[j] > 0: j-- 
    if X[i] + Y[j] < 0: i++ 
Output count 

Answer 5

先取两个数组（A，B）并用成对的和创建一个新的数组（E）。对成对和数组（E）进行排序。对于其余两个数组（C，D）中的每一对数字，检查它们的恭维是否存在于成对和数组（E）中。

复杂度：为O（n^2的log（n））