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个数组长度是相同的）。