NOTES · 学习笔记
三数之和:排序 + 双指针 + 去重
题目
题目:给定整数数组 nums,判断是否存在三元组满足 i、j、k 互不相同,且 nums[i]+nums[j]+nums[k]==0,返回所有和为 0 且不重复的三元组。示例:输入 nums = [-1,0,1,2,-1,-4],输出 [[-1,-1,2],[-1,0,1]]——注意输出的顺序和三元组内的顺序并不重要。
我们看思路:这道题要从一个数组中找到三个数字,相加等于 0,并且不能出现重复。所以我们这样想:先排序,nums 变成 [-4,-1,-1,0,1,2]。排好序后,定义一个 i,再定义一个 left 指针指向 i 后面一位的位置,再定义一个 right 指针指向最后元素的位置。
现在 i 指向 -4,left 指向 -1,right 指向 2。题目要求 i+left+right 等于 0,此时 i=-4,left+right=1,i+left+right<0 无法满足要求。当三个数的和小于 0 时,i 不动,让 left 右移寻找更大的数;只有当前 left 和 right 的搜索结束后,外层循环才会让 i 移动到下一个位置。
i 走到第二位元素 -1 的位置,left 来到第三位元素 -1,right 还是最后一位 2。此时 i+left+right=0 满足条件,输出 [-1,-1,2]。然后 i 走到第二个 -1 再算一遍,会再次得到 [-1,0,1]——和之前找到的答案重复了,所以必须考虑去重。
这道题还需要专门考虑去重的问题。首先是 i 的去重:因为数组已经排好序,相同的数字会挨在一起。如果当前的 nums[i] 和前一个 nums[i-1] 相同,说明我们已经用这个数字作为第一个数寻找过了,再寻找一次就可能得到重复的三元组,直接跳过当前的 i。然后是 left 和 right 的去重:找到答案后,left++ 和 right-- 还有可能出现相同答案,所以也要去重。
func threeSum(nums []int) [][]int {
sort.Ints(nums) // 先将数组从小到大排序,方便后面使用双指针
result := [][]int{} // 定义结果数组,用来保存最后找到的三元组
// i 遍历数组,每次固定一个数
for i := range nums {
// 如果当前 nums[i] 和前一个数一样,说明这个数已经作为第一个数找过了
// 所以直接跳过,避免出现重复的三元组
if i > 0 && nums[i] == nums[i-1] {
continue
}
// left 指向 i 后面的第一个位置
left := i + 1
// right 指向数组最后一个位置
right := len(nums) - 1
// 只要 left 还在 right 的左边,就继续寻找
for left < right {
// 计算三个数的总和
sum := nums[i] + nums[left] + nums[right]
if sum < 0 {
// 总和小于 0,说明三个数加起来太小了
// 数组已经排序,所以让 left 右移,找一个更大的数
left++
} else if sum > 0 {
// 总和大于 0,说明三个数加起来太大了
// 所以让 right 左移,找一个更小的数
right--
} else {
// 总和等于 0,说明找到了一个符合要求的三元组
result = append(result, []int{
nums[i],
nums[left],
nums[right],
})
// left 去重
// 如果 left 后面还是相同的数字,就跳过去
// 避免得到重复的三元组
for left < right && nums[left] == nums[left+1] {
left++
}
// right 去重
// 如果 right 前面还是相同的数字,就跳过去
// 避免得到重复的三元组
for left < right && nums[right] == nums[right-1] {
right--
}
// 找到答案后,两个指针继续向中间移动
left++
right--
}
}
}
// 返回所有找到的三元组
return result
}