我们再来介绍一道题目, 是建立在以前的基础上的, 那就是3数之和的基础上,如果你没看过这个教程的话,记得先补一下
LeetCode 15 - 3数之和 - 解题思路记录 - GoLang
在这道题的基础上,我们来看4数之和的解法应该是什么?
题目
LeetCode 18 4Sum
Given an array nums of n integers and an integer target,
are there elements a, b, c, and d in nums such that a + b + c + d = target?
Find all unique quadruplets in the array which gives the sum of target
「Example」
Given array nums = [1, 0, -1, 0, -2, 2], and target = 0.
A solution set is:
[
[-1, 0, 0, 1],
[-2, -1, 1, 2],
[-2, 0, 0, 2]
]
其实就是给定一个集合,求出当中「4个不重复且等于target的值」
我刚看到这道题目的时候, 我就懵了我想着以3数之和的思维去做,定义4个变量, 后来发现根本行不通
接着自己是在想不出来以后, 尝试找一些答案看看, 后来发现了一个这样子的思路
N数之和
其实这个有很多个解法, 但是没研究其他的 「N/2」化解思路, 我尝试用递归的思想去做这道题目
那就是简化它, 把它从「4->3->2数之和」
看这张图是不是感觉 思路清晰了一下?
虽然我们不会4数,但我们之前都讲过**3数之和「和」2数之和**(还没看的小伙伴记得点进去)
知道了这个套路以后, 我们再来看一下具体代码怎么写
func fourSum(nums []int, target int) [][]int {
sort.Ints(nums)
ans := make([][]int, 0)
for i:=0; i< len(nums)-3; i++{
if i != 0 && nums[i] == nums[i-1]{
continue //为了不重复做同一个数字
}
for j:= i+1; j< len(nums) - 2; j++{
if j!= i+1 && nums[j] == nums[j-1]{
continue//为了不重复做同一个数字
}
left := j+1
right := len(nums)-1
for left < right{
sum := nums[i] + nums[j] + nums[left] + nums[right]
if sum < target{
left += 1
}else if sum > target{
right -= 1
}else{
ans = append(ans, []int{nums[i], nums[j], nums[left], nums[right]})
left += 1
right -=1
for left < right && nums[left] == nums[left-1]{
left += 1
}
for left < right && nums[right] == nums[right+1]{
right -= 1
}
}
}
}
}
return ans
}
具体思路
首先
- 数组进行排序
- 注意外层循环的「len(nums)-3」 以及 内层的 「len(nums)-2」 这两项
- 前者 「减3」 是因为第一层循环只需要到最后「4」个元素
- 后者 「减2」 是因为第二层循环只需要到最后「3」个元素
到了第二层循环, 大家可以认真看, 代码跟「3数之和区别不大」这边就不详细解释了
然而这道题的时间复杂度还是「O(N^3)」 有时间也必须简化一下