题目： 统计一个数组中所有和为0的三整数元组的数目，这个问题是类似三点共线或者三线共面问题的简化版。¹

算法1 （暴力求解）

func ThreeSum(a []int) int {
	N := len(a)
	count := 0

	for i := 0; i < N; i++ {
		for j := i + 1; j < N; j++ {
			for k := j + 1; k < N; k++ {
				if (a[i] + a[j] + a[k]) == 0 {
					count++
				}
			}
		}
	}
	return count
}

非常容易的看到其算法复杂度为$N^3$。

算法2 优化算法

首先将a排序，算法思想是将前两个数字相加a[i]+a[j]，然后在a中寻找这两个数字和的负数，也就是-a[i]-a[j]，如何找到了，且下标大于j，则计数加1。

func ThreeSumFast(a []int) int {
	sort.Ints(a)  // 排序

	N := len(a)
	count := 0

	for i := 0; i < N; i++ {
		for j := i + 1; j < N; j++ {
			if BinarySearch(-a[i]-a[j], a) > j { //二分查找
				count++
			}
		}
	}
	return count
}

这个算法的时间复杂度是$N^2logN$，在我的笔记本上对1000个数字进行处理，运行的时间如下：

ThreeSum took 254.934984ms
ThreeSumFast took 18.43887ms

二分查找算法

unc BinarySearch(key int, a []int) int {
	lo := 0
	hi := len(a) - 1
	var mid int

	for lo <= hi {
		mid = lo + (hi-lo)/2
		if key < a[mid] {
			hi = mid - 1
		} else if key > a[mid] {
			lo = mid + 1
		} else {
			return mid
		}
	}
	return -1
}