鑑於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））