LeetCode，三数之和
力扣题目：
给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
- 来源：力扣（LeetCode）
- 链接：https://leetcode-cn.com/problems/3sum
解题
看到题目是否有点似曾相识(如果您看过我之前的文章的话)，没错，我们之前解过「两数之和」题，两数之和的主要解题思路：
- 使用哈希法，将给定的切片 nums 的索引和值，翻转存入到 map 中：
- 判断 目标值 target - nums 中一个元素 是否存在 map 中；
- 如果存在则找到需要的值并返回；
- 若不存在 map 中，则将遍历中的索引及元素值翻转存入到 map 中。
想了解详情可以看一下原文：传送门点这里。
解题「三数之和」，比较直观的解法就是使用三重循环，分别找出第一、二、三个元素，再判断和是否为零：
func threeSum(nums []int) [][]int {
s := [][]int{}
sort.Ints(nums)
length := len(nums)
for first :=0; first < length-1; first++ {
for second :=1; second < length-1; second++ {
for third :=2; third < length-1; third++ {
if nums[first] + nums[second] + nums[third] == 0 {
s = append(s,[]int{nums[first],nums[second],nums[third]})
}
}
}
}
return s
}
执行结果：
输入
[-1,0,1,2,-1,-4]
输出
[[-1,0,1],[-1,2,-1],[-1,-1,2],[0,1,-1],[0,-1,1],[1,0,-1],[2,-1,-1],[-1,0,1],[-1,2,-1],[-1,-1,2]]
预期结果
[[-1,-1,2],[-1,0,1]]
发现有许多重复的答案，根据题目要求：答案中不可以包含重复的三元组，我们对代码进行改进。
改进
排序 + 双指针
为了保证不重复，我们所枚举的三元组 (a,b,c) 需要满足 a ≤ b ≤ c，保证了只有(a,b,c) 这个顺序会被枚举到，而(b,a,c)、(c,b,a) 等等这些不会，这样就减少了重复。要实现这一点，我们可以将数组中的元素从小到大进行排序，随后使用普通的三重循环就可以满足上面的要求。
同时，对于每一重循环而言，相邻两次枚举的元素不能相同，否则也会造成重复，这时候我们只需要「跳到」下一个不相同的元素即可。
对于三元组，a + b + c = 0，在遍历的时候，我们先确定第一个元素 a ,遍历第二层循环，b 每往后枚举一个元素，由于我们将数组排序过，b 每增大时，仍要满足 a + b + c = 0的条件，那么 c 就需要相应的减小。
也就是说，我们可以从小到大枚举 b，同时从大到小枚举 c，即第二重循环和第三重循环实际上是并列的关系。如此，我们就可以保持第二重循环不变，而将第三重循环变成一个从数组最右端开始向左移动的指针。
func threeSum(nums []int) [][]int {
s := [][]int{}
sort.Ints(nums)
length := len(nums)
// 枚举 a
for first := 0; first < length; first++ {
//每次枚举第一个元素，a 需要和上次使用的元素不同，避免重复
if first > 0 && nums[first] == nums[first - 1] {
continue
}
third := length -1 // c 对应的指针初始指向数组的最右端
target := -1 * nums[first]
//枚举b
for second := first + 1; second < length; second++ {
// b 需要和上一次枚举的数不相同，避免重复
if second > first + 1 && nums[second] == nums[second - 1] {
continue
}
// 需要保证 b 的指针在 c 的指针的左侧
for second < third && nums[second] + nums[third] > target {
third--
}
// 如果指针重合，随着 b 后续的增加
// 就不会有满足 a+b+c=0 并且 b<c 的 c 了，可以退出循环
if second == third {
break
}
if nums[second] + nums[third] == target {
s = append(s, []int{nums[first], nums[second], nums[third]})
}
}
}
return s
}
❝上面解题方法就是我们常说的「双指针」，当我们需要枚举数组中的两个元素时，如果我们发现随着第一个元素的递增，第二个元素是递减的，那么就可以使用双指针的方法。 ❞
腾讯云开发者
