算法

题目：

给定四个列表A，B，C，D的整数值，计算(i, j, k, l)有多少元组，使其A[i] + B[j] + C[k] + D[l]为零。

为了使问题更容易，所有A，B，C，D都具有相同的N长度，其中0≤N≤500。所有整数都在-2 28到2 28 - 1 的范围内，结果保证在大多数2 31 - 1。

示例：

思路：

这是四个元素的数组，首先依次将两个数组的元素互相相加形成两个长度翻倍的数组，然后再对这两个数组进行查询。

对这两个数组进行排序，排完序后一个数组从第一个元素开始，一个数组从最后一个元素开始，依次对元素进行比较。如果第一个元素加上最后一个元素小于0，则第一个元素向前进一个，前提是没有越界，依次循环，知道他们不小于0，然后再比较两个元素和是否大于零，大于零的话则第二个元素后退。知道两个元素相加为0，则比较第一个数组中该元素右边有多少个元素是和该元素相等的，同理比较第二个数组中该元素左边的元素有多少个是和该元素相等的，然后两个元素相乘，即为所要求的个数，然后再加上之前的个数，在进行下一轮的循环。

代码：

int[] m = new int[a.length * b.length], n = new int[c.length * d.length];
		int i = 0;
		for (int ia : a) for (int ib : b) m[i++] = ia + ib;
		i = 0;
		for (int ic : c) for (int id : d) n[i++] = ic + id;
		
		Arrays.sort(m);
		Arrays.sort(n);
		
		int mi = 0, ni = n.length - 1;
		int count = 0;
		while (mi < m.length && ni >= 0) {
			while (mi < m.length && m[mi] + n[ni] < 0) {
				mi++;
			}
			if (mi < m.length) {
				while (ni >= 0 && m[mi] + n[ni] > 0) {
					ni--;
				}
			}
			if (mi < m.length && ni >= 0 && m[mi] + n[ni] == 0) {
				int cm = 1, cn = 1;
				while (mi < m.length - 1 && m[mi] == m[mi + 1]) {
					mi++;
					cm++;
				}
				while (ni > 0 && n[ni] == n[ni - 1]) {
					ni--;
					cn++;
				}
				count += cm * cn;
				mi++;
				ni--;
			}
		}
		return count;
	}
}