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⁵ <= nums[i] <= 10⁵

题解

三数之和很自然的会想到先排序，然后固定一个数，接着使用 left 和 right 分别指向数组的开头和结尾。这样可以控制 nums[left] 和 nums[right] 这两数之和的大小。
如果想让他俩的和大一点，就让 left++，如果想让他俩的和小一点，就让 right--。
在添加三数之和时需要判断是否重复。
不要忘了去重

代码实现

func threeSum(nums []int) [][]int {
	sort.Ints(nums)
	var res [][]int
	for i := 0; i < len(nums); i++ {
		twoSumRes := twoSum(nums, i+1, 0-nums[i])
		for _, twoRes := range twoSumRes {
			var t []int
			t = append(t, nums[i])
			t = append(t, twoRes...)
			if t != nil {
				res = append(res, t)
			}
		}
        // 去重
		for i < len(nums)-1 && nums[i] == nums[i+1] {
			i++
		}
	}
	return res
}

func twoSum(nums []int, start, target int) [][]int {
	low, high := start, len(nums)-1
	var res [][]int
	for low < high {
		sum := nums[low] + nums[high]
		left, right := nums[low], nums[high]
		if sum > target {
			for low < high && nums[high] == right {
				high--
			}
		} else if sum < target {
			for low < high && nums[low] == left {
				low++
			}
		} else if sum == target {
			res = append(res, []int{nums[low], nums[high]})
			// 去重
			for low < high && nums[low] == left {
				low++
			}
			for low < high && nums[high] == right {
				high--
			}
		}
	}
	return res
}