比较好的高端网站制作公司,邵阳网站建设网站,雷山网站建设,135网站模板文章目录18. 四数之和题目描述示例 1#xff1a;示例 2#xff1a;提示#xff1a;解题思路算法一#xff1a;排序 双指针#xff08;推荐#xff09;算法二#xff1a;通用 kSum#xff08;含 2Sum 双指针#xff09;复杂度关键细节代码实现要点完整题解代码18. 四数…
文章目录18. 四数之和题目描述示例 1示例 2提示解题思路算法一排序 双指针推荐算法二通用 kSum含 2Sum 双指针复杂度关键细节代码实现要点完整题解代码18. 四数之和
题目描述
给你一个由 n 个整数组成的数组 nums 和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] 若两个四元组元素一一对应则认为两个四元组重复
0 a, b, c, d na、b、c 和 d 互不相同nums[a] nums[b] nums[c] nums[d] target
你可以按 任意顺序 返回答案 。
示例 1
输入nums [1,0,-1,0,-2,2], target 0 输出[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
示例 2
输入nums [2,2,2,2,2], target 8 输出[[2,2,2,2]]
提示
1 nums.length 200-10^9 nums[i] 10^9-10^9 target 10^9
解题思路
本题是“kSum”系列的典型代表。最直接的思路是
先对数组排序固定两个数用双指针在剩余区间内查找另外两个数3重循环 双指针通过跳过重复元素与剪枝优化保证不重复且加速
此外还可以抽象成通用的 kSum 递归框架当 k2 时用双指针解决否则固定一个元素递归解决 (k-1)Sum。
算法一排序 双指针推荐
排序后外层两重循环固定 i、j内层用左右指针 left、right 搜索两数和使四数之和为 target跳过重复元素i、j、left、right 层面避免重复解剪枝用最小可能和/最大可能和与 target 比较提前 break/continue
flowchart TDA[排序nums] -- B[i从0到n-4]B -- C{去重/剪枝}C --|不满足| BC -- D[j从i1到n-3]D -- E{去重/剪枝}E --|不满足| DE -- F[leftj1,rightn-1]F -- G{leftright?}G --|否| DG -- H[sumnums[i]nums[j]nums[left]nums[right]]H -- I{sumtarget?}I --|是| J[加入解并去重移动]I --|sumtarget| K[left]I --|sumtarget| L[right--]J -- GK -- GL -- G算法二通用 kSum含 2Sum 双指针
排序kSum(nums,k,start,target): 若 k2用双指针在区间 [start,n) 里求两数和为 target 的所有解否则从 start 枚举 i跳过重复元素并递归 kSum(nums,k-1,i1,target-nums[i]) 结合最小/最大可能和剪枝
flowchart TDA[sort(nums)] -- B[kSum(nums,4,0,target)]B -- C{k2?}C --|是| D[2Sum 双指针]C --|否| E[for i from start to n-k]E -- F{跳过重复}F -- EE -- G[递归 kSum(k-1,i1,target-nums[i])]G -- H[前缀拼接nums[i]并收集]H -- E复杂度
排序 双指针时间 O(n^3)空间 O(1)不计结果集kSum最坏也为 O(n^{k-1})本题 k4 即 O(n^3)
关键细节
去重 i0 且 nums[i]nums[i-1] 跳过ji1 且 nums[j]nums[j-1] 跳过命中答案后 left/right 向内移动并跳过相同值 剪枝 对当前固定前缀比较最小可能和与最大可能和与 target 的关系进行 break/continue long 溢出处理 计算和时转为 int64 避免大数相加溢出
代码实现要点
先排序明确单调结构便于双指针严格实现四处去重逻辑保证不重复使用 int64 做加法再比较避免溢出通过下界/上界剪枝减少无效搜索
本仓库 18/main.go 中提供
fourSum排序 双指针实现fourSumKSum kSum通用 kSum 版本主函数内含示例用例并输出结果便于自检
完整题解代码
package mainimport (fmtsort
)// fourSum 经典排序 双指针解法
// 时间复杂度: O(n^3)
// 空间复杂度: O(1)不计结果集
func fourSum(nums []int, target int) [][]int {res : make([][]int, 0)if len(nums) 4 {return res}sort.Ints(nums)n : len(nums)t : int64(target)for i : 0; i n-3; i {// 去重: 固定 iif i 0 nums[i] nums[i-1] {continue}// 剪枝: 最小可能和 target 或 最大可能和 targetminSum : int64(nums[i]) int64(nums[i1]) int64(nums[i2]) int64(nums[i3])if minSum t {break}maxSum : int64(nums[i]) int64(nums[n-1]) int64(nums[n-2]) int64(nums[n-3])if maxSum t {continue}for j : i 1; j n-2; j {// 去重: 固定 jif j i1 nums[j] nums[j-1] {continue}// 剪枝min2 : int64(nums[i]) int64(nums[j]) int64(nums[j1]) int64(nums[j2])if min2 t {break}max2 : int64(nums[i]) int64(nums[j]) int64(nums[n-1]) int64(nums[n-2])if max2 t {continue}left, right : j1, n-1for left right {sum : int64(nums[i]) int64(nums[j]) int64(nums[left]) int64(nums[right])if sum t {res append(res, []int{nums[i], nums[j], nums[left], nums[right]})// 去重移动lv, rv : nums[left], nums[right]for left right nums[left] lv {left}for left right nums[right] rv {right--}} else if sum t {left} else {right--}}}}return res
}// fourSumKSum 通用 kSum 解法入口调用 kSum with k4
func fourSumKSum(nums []int, target int) [][]int {sort.Ints(nums)return kSum(nums, 4, 0, int64(target))
}// kSum 通用递归解法
// nums 已排序寻找从 start 开始 k 个数之和为 target 的所有组合
func kSum(nums []int, k int, start int, target int64) [][]int {res : make([][]int, 0)n : len(nums)if k 2 {// 2Sum 双指针l, r : start, n-1for l r {s : int64(nums[l]) int64(nums[r])if s target {res append(res, []int{nums[l], nums[r]})lv, rv : nums[l], nums[r]for l r nums[l] lv {l}for l r nums[r] rv {r--}} else if s target {l} else {r--}}return res}// 剪枝: 若最小可能和或最大可能和不满足直接返回if start n {return res}minSum : int64(0)for i : 0; i k; i {if starti n {return res}minSum int64(nums[starti])}maxSum : int64(0)for i : 0; i k; i {if n-1-i start {return res}maxSum int64(nums[n-1-i])}if minSum target || maxSum target {return res}for i : start; i n-k; i {if i start nums[i] nums[i-1] {continue}// 递归找 (k-1)Sumpartial : kSum(nums, k-1, i1, target-int64(nums[i]))for _, comb : range partial {res append(res, append([]int{nums[i]}, comb...))}}return res
}func main() {// 示例 1nums1 : []int{1, 0, -1, 0, -2, 2}target1 : 0ans1 : fourSum(nums1, target1)fmt.Printf(示例1(双指针): nums%v target%d\n结果: %v\n\n, nums1, target1, ans1)// 示例 2nums2 : []int{2, 2, 2, 2, 2}target2 : 8ans2 : fourSum(nums2, target2)fmt.Printf(示例2(双指针): nums%v target%d\n结果: %v\n\n, nums2, target2, ans2)// 通用 kSum 版本对比ans1k : fourSumKSum(nums1, target1)ans2k : fourSumKSum(nums2, target2)fmt.Printf(示例1(kSum): %v\n示例2(kSum): %v\n\n, ans1k, ans2k)// 其他用例nums3 : []int{0, 0, 0, 0}target3 : 0fmt.Printf(全零用例: %v\n结果: %v\n\n, nums3, fourSum(nums3, target3))nums4 : []int{-3, -1, 0, 2, 4, 5}target4 : 2fmt.Printf(混合用例: %v target%d\n结果: %v\n, nums4, target4, fourSum(nums4, target4))
}
