15-三数之和.md

15. 三数之和

leecode原题

题目

给你一个包含 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
• -105 <= nums[i] <= 105

解题思路

思路

这道题详细讲解，建议直接参考代码随想录

总体来说:

排序 + 双指针

1. nums从小到大排序，i,j,k分别代表元素a,b,c的索引

2. 先固定i,i的范围是区间[0, len(nums)-2)，注意要对a去重，如果nums[i] == nums[i-1]将可能出现三元组重复

3. 固定i后，取j = i+1,k =len(nums)-1，j和k在j<k的情况下（j>i和j<k已经保证j和k在移动过程中不会数组越界）作为双指针进行遍历，判断a+b+c

• 如果a+b+c==0,则添加三元组,然后j++、k--，并且注意对b,c去重，原因同2中的a

• 如果a+b+c>0,则k--

• 如果a+b+c<0,则j++

实现

源码

func threeSum(nums []int) [][]int {
	// 对数组进行从小到大的排序
	sort.Ints(nums)
	res := make([][]int, 0)

	// 定义三个数begin, left, rigth(i, left, right不能相同)
	for i := 0; i < len(nums)-2; i++ { // begin最多到len(nums)-2
		begin := nums[i]
		// 去除begin的重复值
		if i > 0 && begin == nums[i-1] {
			continue
		}
		left := i + 1          // 左指针指向begin前一位
		right := len(nums) - 1 // 右指针指向最后一位
		for left < right {
			sum := nums[i] + nums[left] + nums[right]
			if sum == 0 {
				res = append(res, []int{nums[i], nums[left], nums[right]})
				// left去重
				curLeftValue := nums[left]
				for left < right && curLeftValue == nums[left] {
					left++
				}
				// right去重
				curRightValue := nums[right]
				for left < right && curRightValue == nums[right] {
					right--
				}
			} else if sum > 0 {
				// 因为数组已经排序, 所以right应该向数值小的地方移动
				right--
			} else {
				// 因为数组已经排序, 所以left应该向数值大的地方移动
				left++
			}
		}

	}
	return res
}