【力扣】15. 三数之和

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。

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

示例 1：

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。

示例 2：

输入：nums = [0,1,1]
输出：[]
解释：唯一可能的三元组和不为 0 。

示例 3：

输入：nums = [0,0,0]
输出：[[0,0,0]]
解释：唯一可能的三元组和为 0 。

提示：

• 3 <= nums.length <= 3000
• -105 <= nums[i] <= 105

题解：

双指针法（左右指针法）：

// 时间复杂度：O(n^2)
// 空间复杂度：O(n^2)
func threeSum(nums []int) [][]int {
	sort.Ints(nums)
	result := make([][]int, 0)
	// 因为是三数之和，除了当前数 nums[i] 以外，还要要留下两个数不做处理，所以这里终止条件是 len(nums)-2
	for i := 0; i < len(nums)-2; i++ {
		// 当前数和上一个数相等则跳过，防止重复
		if i > 0 && nums[i] == nums[i-1] {
			continue
		}
		// 双指针法（左右指针法）去找剩下的两个数
		left, right := i+1, len(nums)-1
		for left < right {
			sum := nums[i] + nums[left] + nums[right]
			if sum == 0 {
				// 匹配到结果了，插入到结果集当中
				result = append(result, []int{nums[i], nums[left], nums[right]})
				left++
				right--
				// 左右两边指针遇到相同数字，则直接跳过去（去重复）
				for left < right && nums[left] == nums[left-1] {
					left++
				}
				for left < right && nums[right] == nums[right+1] {
					right--
				}
			} else if sum < 0 {
				// 三数相加的和小于 0 ，则说明数字太小了，左指针右移让三数之和变大
				left++
			} else {
				// 三数相加的和大于 0 ，则说明数字太大了，右指针左移让三数之和变小
				right--
			}
		}
	}
	return result
}

双指针法（左右指针法）+哈希表法：

// 时间复杂度：O(n^2)
// 空间复杂度：O(n^2)
func threeSum(nums []int) [][]int {
	// 结果集初始化
	var res [][]int

	// 用于记录每个数字出现的次数
	counter := map[int]int{}

	for _, value := range nums {
		counter[value]++
	}

	// 保存唯一数字
	var uniques []int
	for key := range counter {
		uniques = append(uniques, key)
	}

	// 对唯一数字排序
	sort.Ints(uniques)

	for i := 0; i < len(uniques); i++ {
		// 如果数字为 0 0 0，那么添加到结果集
		// 如果数字为 n, n, -2 * n，那么添加到结果集
		if (uniques[i] == 0 && counter[uniques[i]] >= 3) ||
			(uniques[i] != 0 && counter[uniques[i]] > 1 && counter[-2*uniques[i]] > 0) {
			res = append(res, []int{uniques[i], uniques[i], -2 * uniques[i]})
		}
		// 如果这个数字小于0，那么我们需要找到两个数的和为它的相反数
		if uniques[i] < 0 {
			twoSum := -uniques[i]
			// 三个元素的指针分别是：i left right
			left := i + 1
			right := len(uniques) - 1
			// 使用两个指针在剩余的数组中寻找两个数的和为这个数字的相反数
			for left < right {
				if uniques[left]+uniques[right] == twoSum {
					// 找到一组解，添加到结果集
					res = append(res, []int{uniques[i], uniques[left], uniques[right]})
					left++
					right--
				} else if uniques[left]+uniques[right] < twoSum {
					// 如果和小于这个数字的相反数，那么左指针右移
					left++
				} else {
					// 如果和大于这个数字的相反数，那么右指针左移
					right--
				}
			}
		}
	}
	return res
}