题目描述

给定四个包含整数的数组列表 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

解释:
两个元组如下:
1. (0, 0, 0, 1) -> A[0] + B[0] + C[0] + D[1] = 1 + (-2) + (-1) + 2 = 0
2. (1, 1, 0, 0) -> A[1] + B[1] + C[0] + D[0] = 2 + (-1) + (-1) + 0 = 0

算法

本题的解法和前面三数相加的解法类似，都是先对数组排序，然后利用双指针的方法，一个指针指向数组开始，一个指针指向数组末尾，如果相加之和大了，那么就将高位指针向低移动，如果相加之和小了，就将低位指针向高移动

本题和前面的三数之和的区别是这里的指针是在多个数组之上移动，并且有可能有多个同样的元素，遇到这种情况，不同位置的相同元素也要按照两种情况计算，并且如果他们的和已经为0了，但是后续还有可能继续为0，就是低位指针继续向高位移动，高位指针继续向低位移动，在这种情况向下同样可能他们的和为0，这种情况也需要考虑进去

代码

func fourSumCount(A []int, B []int, C []int, D []int) int {
	if len(A) == 0 {
		return 0
	}
	sort.Ints(A)
	sort.Ints(B)
	sort.Ints(C)
	sort.Ints(D)
	count := 0
	for i := 0; i < len(A); i++ {
		for j := 0; j < len(B); j++ {
			tmp := A[i] + B[j]
			low, high := 0, len(D)-1
			for low < len(C) && high >= 0 {
				tmpSum := C[low] + D[high] + tmp
				if tmpSum == 0 {
					// count++
					// 连续有多少个相同的数字
					numC, numD := 0, 0
					for iC := low; iC < len(C); iC++ {
						if C[iC] == C[low] {
							numC++
						} else {
							break
						}
					}
					for iD := high; iD >= 0; iD-- {
						if D[iD] == D[high] {
							numD++
						} else {
							break
						}
					}
					count += (numC * numD)
					low += numC
					high -= numD
				} else if tmpSum < 0 {
					low++
				} else {
					high--
				}
			}
		}
	}
	return count
}