高频算法面试题（二十九）-数组中相加和为0的三元组

「这是我参与11月更文挑战的第 15 天，活动详情查看：2021最后一次更文挑战」

刷算法题，从来不是为了记题，而是练习把实际的问题抽象成具体的数据结构或算法模型，然后利用对应的数据结构或算法模型来进行解题。个人觉得，带着这种思维刷题，不仅能解决面试问题，也能更多的学会在日常工作中思考，如何将实际的场景抽象成相应的算法模型，从而提高代码的质量和性能

数组中相加和为0的三元组

题目来源：LeetCode-15. 三数之和

题目描述

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c =0 ？请你找出所有和为 0 且不重复的三元组

注意：答案中不可以包含重复的三元组

示例

示例 1

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
复制代码

示例 2

输入：nums = []
输出：[]
复制代码

示例 3

输入：nums = [0]
输出：[]
复制代码

提示：

• 0 <= nums.length <= 3000
• 10^5 <= nums[i] <= 10^5

解题

解法一：暴力解法

思路

暴力解法比较容易想到，三重循环搞定。但是会发现题目中要求，不能包含重复的解，什么是重复的解，以例1为例

输入：nums = [-1,0,1,2,-1,-4]
暴力解法，求出的解
[-1.0,1]
[-1,2,-1]
[-1,-1,2]
......
复制代码

我们可以看到[-1,2,-1]和[-1,-1,2]就是重复的解，那如何去除重复的解？这个可以通过排序来实现（反正我是想不到），如果开始就把这些数字先排好序，那相同的元素肯定就连续的在一起了，当我们遍历下一个元素的时候，发现与我上一次遍历的相同，那我就可以不用再考虑这个元素了，直接跳过。语言描述可能不清楚，看下边代码（附上注释）

虽然能解，但是时间复杂度比较高，是O(N^3)

代码

//暴力解法
func ThreeSum(nums []int) [][]int {
	if len(nums) < 3 {
		return [][]int{}
	}

	//排序
	sort.Ints(nums)
	n := len(nums)
	res := [][]int{}
	for i:=0; i < n; i++  {
		//如果当前元素和上一个元素相同，则跳过（避免重复）
		if i > 0 && nums[i] == nums[i-1]  {
			continue
		}
		for j := i + 1; j < n; j++ {
			//如果当前元素和上一个元素相同，则跳过（避免重复）
			if j > i + 1 && nums[j] == nums[j-1] {
				continue
			}
			for k := j + 1; k < n; k++ {
				//如果当前元素和上一个元素相同，则跳过（避免重复）
				if k > j + 1 && nums[k] == nums[k-1] {
					continue
				}
				if (nums[i] + nums[j] + nums[k]) == 0 {
					res = append(res, []int{nums[i], nums[j], nums[k]})
				}
			}
		}
	}

	return res
}
复制代码

解法二：排序 + 双指针

思路

有了上边的思路，看一下还能不能优化

首先为了避免重复，还是先对数据进行排序

当我们确定了第一个元素，那其实，剩下的就是在剩余元素中找到两个数字，使得这两个数字的和等于目标值，这就和之前做过的两数之和很相似了，与两数之和不同的是，我们需要找两个数字，此时可以利用双指针

因为数据是已经排好序的，用两个指针，一个指向开始，一个指向末尾，当它们的和大于目标值的时候，末尾的指针往前移动。当他们的和小于目标值的时候，开始的指针往后移动，直到它们相遇

期间和为目标值的，就是我们想要的结果，具体情况看代码，必要的地方会加注释

代码

func ThreeSum2(nums []int) [][]int {
	if len(nums) < 3 {
		return [][]int{}
	}

	//排序
	sort.Ints(nums)
	n := len(nums)
	res := [][]int{}

	for first := 0; first < n; first ++ {
		//如果和上一个数字相等，跳过（避免重复）
		if first > 0 && nums[first] == nums[first-1] {
			continue
		}
		third := n-1 // 指向最后一个元素（利用双指针）
		target := -1 * nums[first] //我们要找的第二个和第三个数的和，一定是和第一个数互为相反数的，因此这里取反，target = nums[first] + nums[second]

		//second就是指向数组开头的那个指针
		for second := first + 1; second < n; second++ {
			if second > first +1 && nums[second] == nums[second-1] {
				continue
			}
			//如果第二个和第三个数字的和大于目标值，后边那个指针向前移动（因为现在数字是有序的）
			for second < third && nums[second] + nums[third] > target {
				third--
			}
			if second == third { //说明元素遍历完了
				break
			}
			if nums[second] + nums[third] == target {
				res = append(res, []int{nums[first], nums[second], nums[third]})
			}
		}
	}

	return res
}
复制代码