15. 三数之和
题目描述：
给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。
注意：答案中不可以包含重复的三元组。
示例：
给定数组 nums = [-1, 0, 1, 2, -1, -4]，
满足要求的三元组集合为：
[
[-1, 0, 1],
[-1, -1, 2]
]
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/3sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。V1 版本
func threeSum(nums []int) [][]int {
dumplicate := make(map[string]bool)
res := [][]int{}
l := len(nums)
for i := 0; i < l; i++{
for j := i + 1; j < l; j++{
for k := j + 1; k < l; k++{
if nums[i] + nums[j] + nums[k] == 0{
ma, me, mi := sort3(nums[i], nums[j], nums[k])
str := strconv.FormatInt(int64(ma), 10) + strconv.FormatInt(int64(me), 10) + strconv.FormatInt(int64(mi), 10)
if dumplicate[str]{
continue
}
dumplicate[str] = true
res = append(res, []int{nums[i], nums[j], nums[k]})
}
}
}
}
return res
}这个版本的代码使用了遍历的方法，通过维护一个map来去重，时间复杂度是O(n^3)。虽然运行结果正确但是，超时了 …
V1版本显然不是一个好办法，输入3000个数字在我的i7 8700上的耗时高达2.8S，O(n^3)的时间复杂度如果将输入的数字再提高一倍，耗时则达到了22s，这是不可接受的。
再次重申算法的核心其实和做事差不多，就是要少做事情，少做无效的事情，只做有效的事情。这个算法怎样才能变得高效呢？在V1版本中，不仅仅使用了三重循环，还用了一个map来维护去重，能否将这个map去掉呢？
可行的，如果我们遍历的每一个三数组合都是唯一的组合，自然就不存在去重的问题了。
能否将三重循环的复杂度降低呢？如果仔细观察会发现也是可行的，当我们在第一重循环(a1)和第二重循环(a2)的数字确定之后，通过 0 – a1 – a2 即可推算出第三重循环的数字是多少了，其实根本不需要第三重循环。
下面这个V2版本是我的第二个版本，运用了通过以上的改进，同时在第三重循环的位置使用了一个子算法二分查找，速度有了量级的提升。
V2 版本
func threeSum2(nums []int) [][]int {
sort.Ints(nums)
l := len(nums)
res := [][]int{}
for i := 0; i < l; i++{
if i == 0 || nums[i] != nums[i - 1]{
for j := i + 1; j < l; j++{
if j == i + 1 || nums[j] != nums[j - 1]{
target := 0 - nums[i] - nums[j]//搜索的目标值
k := l - 1//从末尾查询
for j < k && nums[k] > target{
k--
}
if k == j{
break
}
if nums[k] == target{
res = append(res, []int{nums[i], nums[j], nums[k]})
}
//target := 0 - nums[i] - nums[j]//搜索的目标值
//lo := j + 1//搜索开始区间
//hi := l - 1//搜索结束区间
//
////二分法搜索k区间的剩余的值
//if lo >= l || nums[lo] > target || nums[hi] < target{
// continue
//}
//
//middle := (lo + hi) / 2
//for middle <= hi && middle >= lo{
// if nums[middle] > target{
// hi = middle - 1
// middle = (middle - 1 + lo) / 2
// } else if nums[middle] < target{
// lo = middle + 1
// middle = (middle + 1 + hi) / 2
// } else {
// //搜索到目标值
// res = append(res, []int{nums[i], nums[j], nums[middle]})
// break
// }
//}
}
}
}
}
return res
}当我将这个版本的代码提交之后到LeetCode之后，发现速度居然只有官方答案的一半，这可不能忍。于是对比了官方的方法，发现还有一个信息没有利用起来，导致我费劲还不讨好。下面的是V3 版本，我花费了很多时间去对比我和官方的差异，甚至都开始怀疑是不是官方的测试数据是有利于官方算法的，终于在k := l – 1那一行代码发现了玄机，k 一定程度上决定着第三重循环也就是被执行次数最多的循环的遍历次数，由于随着j的增加，我们预期的答案值一定是在逐步递减的，所以对于更大的j，k的值不可能比上一次更高，这个问题就变成了遍历 l 的长度，获得n个解，效率胜出了我的二分查找，既简洁又美。而我的做法是运行了n次二分查找。
V3版本
func threeSum(list []int)[][]int {
sort.Ints(list)
l := len(list)
res := make([][]int, 0)
for i := 0; i < l; i++{
if i != 0 && list[i] == list[i - 1]{
continue
}
target := 0 - list[i]
k := l - 1
for j := i + 1; j < l; j++{
if j != i + 1 && list[j] == list[j - 1]{
continue
}
for k > j && list[k] + list[j] > target {
k--
}
if k == j{
break
}
if target == list[k] + list[j]{
res = append(res, []int{list[i], list[j], list[k]})
}
}
}
return res
}对此，我当然不死心，于是又写了第四个版本，将从官方版本答案中发现的信息利用到了我的二分查找版本中，得到了下面的V4，很遗憾的是 V4的效率也略低于官方版本（在我的测试数据下）10%，我认为是缩小二分查找的范围对于二分查找的提升并不明显，二分查找擅长于提升大范围查找的性能。
V4版本
func threeSum2(nums []int) [][]int {
sort.Ints(nums)
l := len(nums)
res := [][]int{}
for i := 0; i < l; i++{
if i == 0 || nums[i] != nums[i - 1]{
hi := l - 1//搜索结束区间
for j := i + 1; j < l; j++{
if j == i + 1 || nums[j] != nums[j - 1]{
lo := j + 1//搜索开始区间
target := 0 - nums[i] - nums[j]//搜索的目标值
//二分法搜索k区间的剩余的值
if lo >= l || nums[lo] > target || nums[hi] < target{
continue
}
middle := (lo + hi) / 2
for middle <= hi && middle >= lo{
if nums[middle] > target{
hi = middle - 1
middle = (middle - 1 + lo) / 2
} else if nums[middle] < target{
lo = middle + 1
middle = (middle + 1 + hi) / 2
} else {
//搜索到目标值
res = append(res, []int{nums[i], nums[j], nums[middle]})
break
}
}
if middle <= j + 1{
break
}
}
}
}
}
return res
}仅仅一行代码的位置之差，性能数倍之差。这一方面说明了写代码时需要在意细节，另一方面也说明了学会问题本质的重要性。