LeetCode 18 - 4数之和 - 解题思路记录 - Golang

960 阅读3分钟

我们再来介绍一道题目, 是建立在以前的基础上的, 那就是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) 有时间也必须简化一下

其他相关题目连接

LeetCode 55 - 跳跃游戏 - 解题思路记录(动态规划优化版) - GoLang

LeetCode 55 - 跳跃游戏 - 解题思路记录(递归+动态规划法) - Golang

LeetCode 53 - 最大子序和 - 解题思路记录(附带动态规划) - GoLang

LeetCode 49 - 字母异位词分组 - 解题思路记录 - Golang

LeetCode 21 - 合并有序链表 - 解题思路记录 - GoLang

LeetCode 2 - 两数之和 - 解题思路记录 - GoLang

LeetCode 12 - 罗马数字 - 解题思路记录 - GoLang

LeetCode 15 - 3数之和 - 解题思路记录 - GoLang

LeetCode 5 - 回文串 - 解题思路记录 - GoLang

Github代码集合