2.4　四數相加II

題目描述（第454題）

給定4個包含整數的數組列表A、B、C、D，計算有多少個元組(i,j,k,l)能使A[i]+B[j]+C[k]+D[l]=0。

為了使問題簡單化，所有的A、B、C、D具有相同的長度n，且0≤n≤500。所有整數的范圍在-228到228-1之間，最終結果不會超過231-1。

示例

輸入：A=[1,2]，B=[-2,-1]，C=[-1,2]，D=[0,2]

輸出：2

解釋：

兩個元組如下。

●　(0,0,0,1)→A[0]+B[0]+C[0]+D[1]=1+(-2)+(-1)+2=0

●　(1,1,0,0)→A[1]+B[1]+C[0]+D[0]=2+(-1)+(-1)+0=0

這是四數之和的第2個版本。這道題不再是1個數組，而是4個數組，并在每個數組中挑選一個數，使其相加等于0。

思路

類似地，我們仍然可以固定兩個元素，然后將所有的兩兩組合存起來，然后去尋找另外兩個元素。這樣的時間復雜度為O(n2)。如果你愿意的話，也可以固定1個元素然后尋找3個元素，但是這樣的時間復雜度是O(n3)。

代碼

復雜度分析

●　時間復雜度：O(n2)。

●　空間復雜度：我們使用mapper來存儲A和B兩兩相加的結果，因此空間復雜度為O(n)，其中n為數組長度（題目限定了A、B、C、D 這4個數組長度是相同的）。