「这是我参与11月更文挑战的第 15 天,活动详情查看:2021最后一次更文挑战」
刷算法题,从来不是为了记题,而是练习把实际的问题抽象成具体的数据结构或算法模型,然后利用对应的数据结构或算法模型来进行解题。个人觉得,带着这种思维刷题,不仅能解决面试问题,也能更多的学会在日常工作中思考,如何将实际的场景抽象成相应的算法模型,从而提高代码的质量和性能
数组中相加和为0的三元组
题目来源:LeetCode-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^5 <= nums[i] <= 10^5
解题
解法一:暴力解法
思路
暴力解法比较容易想到,三重循环搞定。但是会发现题目中要求,不能包含重复的解,什么是重复的解,以例1为例
输入:nums = [-1,0,1,2,-1,-4]
暴力解法,求出的解
[-1.0,1]
[-1,2,-1]
[-1,-1,2]
......
复制代码
我们可以看到[-1,2,-1]和[-1,-1,2]就是重复的解,那如何去除重复的解?这个可以通过排序来实现(反正我是想不到),如果开始就把这些数字先排好序,那相同的元素肯定就连续的在一起了,当我们遍历下一个元素的时候,发现与我上一次遍历的相同,那我就可以不用再考虑这个元素了,直接跳过。语言描述可能不清楚,看下边代码(附上注释)
虽然能解,但是时间复杂度比较高,是O(N^3)
代码
//暴力解法
func ThreeSum(nums []int) [][]int {
if len(nums) < 3 {
return [][]int{}
}
//排序
sort.Ints(nums)
n := len(nums)
res := [][]int{}
for i:=0; i < n; i++ {
//如果当前元素和上一个元素相同,则跳过(避免重复)
if i > 0 && nums[i] == nums[i-1] {
continue
}
for j := i + 1; j < n; j++ {
//如果当前元素和上一个元素相同,则跳过(避免重复)
if j > i + 1 && nums[j] == nums[j-1] {
continue
}
for k := j + 1; k < n; k++ {
//如果当前元素和上一个元素相同,则跳过(避免重复)
if k > j + 1 && nums[k] == nums[k-1] {
continue
}
if (nums[i] + nums[j] + nums[k]) == 0 {
res = append(res, []int{nums[i], nums[j], nums[k]})
}
}
}
}
return res
}
复制代码
解法二:排序 + 双指针
思路
有了上边的思路,看一下还能不能优化
首先为了避免重复,还是先对数据进行排序
当我们确定了第一个元素,那其实,剩下的就是在剩余元素中找到两个数字,使得这两个数字的和等于目标值,这就和之前做过的两数之和很相似了,与两数之和不同的是,我们需要找两个数字,此时可以利用双指针
因为数据是已经排好序的,用两个指针,一个指向开始,一个指向末尾,当它们的和大于目标值的时候,末尾的指针往前移动。当他们的和小于目标值的时候,开始的指针往后移动,直到它们相遇
期间和为目标值的,就是我们想要的结果,具体情况看代码,必要的地方会加注释
代码
func ThreeSum2(nums []int) [][]int {
if len(nums) < 3 {
return [][]int{}
}
//排序
sort.Ints(nums)
n := len(nums)
res := [][]int{}
for first := 0; first < n; first ++ {
//如果和上一个数字相等,跳过(避免重复)
if first > 0 && nums[first] == nums[first-1] {
continue
}
third := n-1 // 指向最后一个元素(利用双指针)
target := -1 * nums[first] //我们要找的第二个和第三个数的和,一定是和第一个数互为相反数的,因此这里取反,target = nums[first] + nums[second]
//second就是指向数组开头的那个指针
for second := first + 1; second < n; second++ {
if second > first +1 && nums[second] == nums[second-1] {
continue
}
//如果第二个和第三个数字的和大于目标值,后边那个指针向前移动(因为现在数字是有序的)
for second < third && nums[second] + nums[third] > target {
third--
}
if second == third { //说明元素遍历完了
break
}
if nums[second] + nums[third] == target {
res = append(res, []int{nums[first], nums[second], nums[third]})
}
}
}
return res
}
复制代码
近期评论