给你一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?请你找出所有和为 0 且不重复的三元组。
注意:答案中不可以包含重复的三元组。
看到题目是否有点似曾相识(如果您看过我之前的文章的话),没错,我们之前解过「两数之和」题,两数之和的主要解题思路:
想了解详情可以看一下原文:传送门点这里。
解题「三数之和」,比较直观的解法就是使用三重循环,分别找出第一、二、三个元素,再判断和是否为零:
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
}
❝上面解题方法就是我们常说的「双指针」,当我们需要枚举数组中的两个元素时,如果我们发现随着第一个元素的递增,第二个元素是递减的,那么就可以使用双指针的方法。 ❞