给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。
//调用三数和的APIfunc fourSum(nums []int, target int) [][]int {sort.Sort(sort.IntSlice(nums)) // 从小到大排序ret := make([][]int,0)for i := 0; i < len(nums)-3; i++ {// if nums[i] > target { break }if i > 0 && nums[i] == nums[i-1] { continue } // i去重threeRet := threeSum(nums[i+1:len(nums)], target-nums[i])if len(threeRet) == 0 { continue }for _, value := range threeRet {tmp := make([]int,3)copy(tmp,value)tmp = append(tmp, nums[i])ret = append(ret, tmp)}}return ret}func threeSum(nums []int, target int) [][]int {if len(nums) < 3 { return [][]int{} }ret := make([][]int, 0, 0)// 从最左侧开始固定，l r为固定i后开始对右侧部分遍历for i := 0; i < len(nums) - 1; i++ {l, r := i + 1, len(nums) - 1// if nums[i] > target || nums[i] + nums[l] > target { break } // 优化掉不可能的情况if i > 0 && nums[i] == nums[i-1] { continue } // i 去重 如果nums[i-1]时已考虑了nums[i]的全部情况for l < r {if l > i + 1 && nums[l] == nums[l-1] { // l 去重l++; continue}if r < len(nums) - 2 && nums[r] == nums[r+1] { // r 去重r--; continue}if nums[i] + nums[l] + nums[r] > target { //r--} else if nums[i] + nums[l] + nums[r] < target {l++} else {ret = append(ret, []int{nums[i], nums[l], nums[r]})l++; r--}}}return ret}
//滑动窗口 + 二分法查找指定数值
func fourSum(nums []int, target int) [][]int {
i := 0 // 左指针
j := 0 // 右指针
mid := 0 // 中间值指针
midLeft := 0
midRight := 0
numsLen := len(nums)
result := make([][]int,0,0)
if numsLen < 4 { // 元素数不符合
return result
}
sortNums := sort.IntSlice(nums)
sortNums.Sort()
for k := 0; k < numsLen - 3 /* 如果后面不够4个元素 提前结束*/; k++ {
if k >0 && nums[k] == nums[k - 1] { // 当前元素与上个元素重复，不用在查找， 因为查到的也是一样的数据
continue
}
if nums[k] + nums[k+1] + nums[k+2] + nums[k+3] > target { // 最小四个值之和 大于目标值
return result
}
mid = 0
midLeft = 0
midRight = 0
for i = k+1; i < numsLen - 2 /*保证i后面至少还需要2个元素*/; i++ {
if i > k + 1 && nums[i] == nums[i - 1] { // 当前元素与上个元素重复，不用在查找， 因为查到的也是一样的数据
continue
}
j = numsLen - 1
for i < j-1 {
if nums[k] + nums[i] + nums[j] + nums[j-1] < target {
break
}
if nums[k] + nums[i] + nums[j] >= target && nums[i] > 0 {
j--
continue
}
needNumber := target - ( nums[k] + nums[i] + nums[j] )
// nums[k] + nums[i] + nums[j] < target
// 在 (i,j)内找到一个符合 nums[k] + nums[i] + nums[j] + nums[mid] == target即可
midLeft = i+1
midRight = j-1
// 二分查找 查到符合的值
for midLeft <= midRight {
mid = midLeft + ( (midRight - midLeft) >> 1)
if nums[mid] > needNumber {
midRight = mid - 1
continue
}
if nums[mid] < needNumber {
midLeft = mid + 1
continue
}
if nums[mid] == needNumber {
// 跳过重复的
lastIndex := len(result) - 1
if lastIndex >= 0 && result[lastIndex][0] == nums[k] &&
result[lastIndex][1] == nums[i] &&
result[lastIndex][2] == nums[mid] &&
result[lastIndex][3] == nums[j]{
break
}
result = append(result, []int{
nums[k],
nums[i],
nums[mid],
nums[j],
})
break
}
}
j--
}
}
}
return result
}
//三数之和➕一层固定判断
func fourSum(nums []int, target int) [][]int {
// 对数组进行排序
Sort(nums)
n := len(nums)
// 定义返回的数组
result := make([][]int, 0)
// 从数组左侧开始进行遍历,固定左侧第一个值
for i := 0; i < n - 3; i++ {
// 如果最小值都大于0，则整个数组都没有符合要求的组合
if nums[i] + nums[i+1] + nums[i+2] + nums[3] > target {
break
}
// 确保nums[i]改变了
if i > 0 && nums[i] == nums[i-1] {
continue
}
// 固定第二个值，第二个值都取值范围为外循环左侧+1到外循环右侧-1
// 这里其实可以理解为对三数求和了,步骤与三数求和一致了
for b := i + 1; b < (n - 2); b++ {
// 去重
if b > i + 1 && nums[b] == nums[b-1] {
continue
}
//左右两侧都固定好了，用左指针和右指针夹逼
L := b + 1
R := n - 1
for L < R {
sum := nums[i] + nums[b] + nums[L] + nums[R]
if sum == target {
// 保存四个数
item := make([]int, 4)
item[0] = nums[i]
item[1] = nums[b]
item[2] = nums[L]
item[3] = nums[R]
result = append(result, item)
// 左指针去重
for L < R && nums[L] == nums[L+1] {
L++
}
// 右指针去重
for L < R && nums[R] == nums[R-1]{
R--
}
R--
L++
} else if sum > target {
// 和比目标值大，因为左侧如果继续右移，值只会比当前值大，所以需要右指针变小//左移动
R--
} else {
L++
}
}
}
}
return result
}
func Sort(nums []int) {
sort(nums, 0, len(nums) - 1)
}
func sort(nums []int, start int, end int) {
if start >= end {
return
}
i := cut(nums, start, end)
sort(nums, start, i - 1)
sort(nums, i + 1, end)
}
func cut(arr []int, start int, end int) int {
pivot := arr[end]
p := start
q := start
for ; q < end; q++ {
if arr[q] < pivot {
arr[p], arr[q] = arr[q], arr[p]
p++
}
}
arr[p], arr[end] = arr[end], arr[p]
return p
}
若有收获，就点个赞吧
0 人点赞
