LeetCode-Go 题解 18. 4Sum三种去重方案实现四数之和【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go本篇文章以 LeetCode-Go 仓库中 0018.4Sum 官方题解 为主线深入剖析 4Sum 问题中“去重”这一核心难点完整还原仓库实现的三种解法双指针、kSum 递归泛化与计数 map 枚举并结合 18. 4Sum.go 源码与 18. 4Sum_test.go 测试用例给出可复现、可验证的实战方案。读完本文你将掌握 N 数之和问题从 2Sum 到 kSum 的完整推导链并理解在 Go 中如何保证解集不重复。一、题目回顾在 n 个整数中寻找和为 target 的四元组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.注意Note解集中不得包含重复的四元组The solution set must not contain duplicate quadruplets。官方给出的示例输入输出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] ]题目大意见 README.md给定一个数组要求在这个数组中找出 4 个数之和为 0 的所有组合。二、核心难点输出解集必须去重4Sum 与 2Sum、3Sum 的最大区别在于去重难度呈指数级上升。原题解0018.4Sum.md 的 “Solution Approach / 解题思路” 一节明确指出数组中同一个数字可能出现多次同一个数字也可能被多次选用但最终输出的解不能重复。例如[-1, 1, 2, -2]、[2, -1, -2, 1]、[-2, 2, -1, 1]属于同一组解即使-1、-2在数组中出现了 100 次、每次使用的下标都不同也不能分别输出因此解题必须同时依赖排序与去重两条手段。三、解法一排序 双指针推荐O(n³)这是仓库中标注为“解法一 双指针”的默认实现对应 18. 4Sum.go也是 3Sum 双指针思路向 4Sum 的自然推广。3.1 核心流程先对数组nums升序排序固定最外层索引i四元组第一个数内层固定索引j第二个数对剩余的区间[j1, n-1]使用left、right双指针相向扫描寻找nums[i] nums[j] nums[left] nums[right] target的组合命中后移动指针并跳过所有相邻的重复值从而保证解不重复。func fourSum(nums []int, target int) (quadruplets [][]int) { sort.Ints(nums) n : len(nums) for i : 0; i n-3 nums[i]nums[i1]nums[i2]nums[i3] target; i { if i 0 nums[i] nums[i-1] || nums[i]nums[n-3]nums[n-2]nums[n-1] target { continue } for j : i 1; j n-2 nums[i]nums[j]nums[j1]nums[j2] target; j { if j i1 nums[j] nums[j-1] || nums[i]nums[j]nums[n-2]nums[n-1] target { continue } for left, right : j1, n-1; left right; { if sum : nums[i] nums[j] nums[left] nums[right]; sum target { quadruplets append(quadruplets, []int{nums[i], nums[j], nums[left], nums[right]}) for left; left right nums[left] nums[left-1]; left { } for right--; left right nums[right] nums[right1]; right-- { } } else if sum target { left } else { right-- } } } } return }3.2 去重与剪枝细节解读这段代码在可读性之外隐藏了三个对性能影响巨大的细节逐个拆解1外层i的去重与“最小可达值”剪枝for i : 0; i n-3 nums[i]nums[i1]nums[i2]nums[i3] target; i {i n-3保证i后面至少还能取 3 个数nums[i]nums[i1]nums[i2]nums[i3] target前四个最小数的和已经大于 target说明以当前i及之后任意位置开头的四元组都不可能再等于 target直接终止外层循环剪枝。if i 0 nums[i] nums[i-1] || nums[i]nums[n-3]nums[n-2]nums[n-1] target { continue }i 0 nums[i] nums[i-1]跳过与上一个相同的固定值避免产生重复四元组nums[i]nums[n-3]nums[n-2]nums[n-1] target当前i与数组最大的三个数相加仍小于 target说明i太小无论如何组合都不可能达到 target直接跳过注意这里用了短路||会先判去重再判剪枝。2内层j的对称去重与剪枝for j : i 1; j n-2 nums[i]nums[j]nums[j1]nums[j2] target; j {j n-2保证j后面还能取 2 个数nums[i]nums[j]nums[j1]nums[j2] target固定i, j后能取到的最小两数和若已超过剩余额度则终止内层循环。if j i1 nums[j] nums[j-1] || nums[i]nums[j]nums[n-2]nums[n-1] target { continue }j i1 nums[j] nums[j-1]跳过重复的第二个固定值nums[i]nums[j]nums[n-2]nums[n-1] target固定i, j后与最大的两个数相加仍小于 target说明j太小跳过。3双指针区间的双重去重命中sum target后for left; left right nums[left] nums[left-1]; left { } for right--; left right nums[right] nums[right1]; right-- { }先移动指针再跳过所有与刚选中值相同的元素——左右两侧各自吃掉连续重复段。测试用例中特意加入了{1, 1, 3, 4, 5, 5}, 10这类**右端存在重复值5, 5**的输入用于覆盖右指针nums[right] nums[right1]的去重分支见 18. 4Sum_test.go 的注释。当sum target时left当sum target时right--利用排序数组的单向移动性保证每个合法组合至多被枚举一次。3.3 复杂度时间复杂度O(n³)。外层两重循环嵌套双指针线性扫描空间复杂度O(n)排序所需空间忽略输出。该复杂度标注与仓库 Two_Pointers 分类表 中对 0018 的记录一致表中标注 O(n³) / O(n)。四、解法二kSum 递归泛化一码通吃 k 数之和仓库中“解法二 kSum”将 4Sum 抽象成通用的 kSum 递归框架18. 4Sum.go当k 2时退化为经典双指针 twoSum。4.1 入口与递归框架func fourSum1(nums []int, target int) [][]int { res, cur : make([][]int, 0), make([]int, 0) sort.Ints(nums) kSum(nums, 0, len(nums)-1, target, 4, cur, res) return res } func kSum(nums []int, left, right int, target int, k int, cur []int, res *[][]int) { if right-left1 k || k 2 || target nums[left]*k || target nums[right]*k { return } if k 2 { // 2 sum twoSum(nums, left, right, target, cur, res) } else { for i : left; i len(nums); i { if i left || (i left nums[i-1] ! nums[i]) { next : make([]int, len(cur)) copy(next, cur) next append(next, nums[i]) kSum(nums, i1, len(nums)-1, target-nums[i], k-1, next, res) } } } }4.2 三个关键设计剪枝条件进入递归前一次性判断if right-left1 k || k 2 || target nums[left]*k || target nums[right]*k { return }right-left1 k剩余区间元素个数不足 k 个k 2递归底线target nums[left]*k区间最小 k 个数的和已超过 targettarget nums[right]*k区间最大 k 个数的和仍不足 target。去重策略在for i : left; i len(nums); i中只有i left或nums[i-1] ! nums[i]时才进入下一层即同一层跳过重复的固定元素这是保证全局解不重复的核心。路径传递cur切片通过copy复制后追加当前选中的数再传入下一层避免递归回溯时共享底层数组导致结果互相污染res使用*[][]int指针在所有递归层之间共享收集结果。4.3 底层的 twoSumfunc twoSum(nums []int, left, right int, target int, cur []int, res *[][]int) { for left right { sum : nums[left] nums[right] if sum target { cur append(cur, nums[left], nums[right]) temp : make([]int, len(cur)) copy(temp, cur) *res append(*res, temp) // reset cur to previous state cur cur[:len(cur)-2] left right-- for left right nums[left] nums[left-1] { left } for left right nums[right] nums[right1] { right-- } } else if sum target { left } else { right-- } } }命中后先copy一份快照写入res再将cur通过cur cur[:len(cur)-2]回退到进入前的状态代码注释明确标注了// reset cur to previous state保证上层递归继续遍历时路径状态正确。五、解法三计数 map 排序去重面向去重设计的枚举仓库中“解法三”采用先统计频次、再按去重后的值枚举的思路18. 4Sum.go这也是原题解在“Solution Approach”中描述的核心思路Use a map to precompute and store the sums of any 3 numbers, which can reduce the time complexity to O(n³). ... map 记录每个数字出现的次数然后对 map 的 key 数组进行排序最后在这个排序以后的数组里面扫找到另外 3 个数字能和自己组成 0 的组合。5.1 预处理频次统计 key 排序counter : map[int]int{} for _, value : range nums { counter[value] } uniqNums : []int{} for key : range counter { uniqNums append(uniqNums, key) } sort.Ints(uniqNums)先统计每个数值出现次数再取所有不同的 key 排序。之后所有枚举都基于去重后的uniqNums天然杜绝了因相同数值不同下标产生的重复解。5.2 分情况枚举四元组的五种“频次形态”因为四元组中可能包含重复值代码按重复形态分类处理1四个相同x*4 target且counter[x] 4if (uniqNums[i]*4 target) counter[uniqNums[i]] 4 { res append(res, []int{uniqNums[i], uniqNums[i], uniqNums[i], uniqNums[i]}) }2三个相同 一个不同两类x*3y target要求counter[x] 2if (uniqNums[i]*3uniqNums[j] target) counter[uniqNums[i]] 2 { res append(res, []int{uniqNums[i], uniqNums[i], uniqNums[i], uniqNums[j]}) } if (uniqNums[j]*3uniqNums[i] target) counter[uniqNums[j]] 2 { res append(res, []int{uniqNums[i], uniqNums[j], uniqNums[j], uniqNums[j]}) }3两两相同x*2y*2 target要求两个数的频次都 1if (uniqNums[j]*2uniqNums[i]*2 target) counter[uniqNums[j]] 1 counter[uniqNums[i]] 1 { res append(res, []int{uniqNums[i], uniqNums[i], uniqNums[j], uniqNums[j]}) }4两个相同 两个不同三类形如x,x,y,z要求counter[x] 1if (uniqNums[i]*2uniqNums[j]uniqNums[k] target) counter[uniqNums[i]] 1 { res append(res, []int{uniqNums[i], uniqNums[i], uniqNums[j], uniqNums[k]}) } if (uniqNums[j]*2uniqNums[i]uniqNums[k] target) counter[uniqNums[j]] 1 { res append(res, []int{uniqNums[i], uniqNums[j], uniqNums[j], uniqNums[k]}) } if (uniqNums[k]*2uniqNums[i]uniqNums[j] target) counter[uniqNums[k]] 1 { res append(res, []int{uniqNums[i], uniqNums[j], uniqNums[k], uniqNums[k]}) }5四个互不相同三数确定后反推第四个c : target - uniqNums[i] - uniqNums[j] - uniqNums[k] if c uniqNums[k] counter[c] 0 { res append(res, []int{uniqNums[i], uniqNums[j], uniqNums[k], c}) }注意这里用c uniqNums[k]约束第四个数必须严格大于第三个数从而保证(i, j, k, c)组合的枚举顺序唯一、互不重复——这是比单纯查频次更精妙的一层去重。该解法在去重思想上与仓库中 3Sum 的“解法二”完全同构对比 15. 3Sum.go同样统计频次、排序 key、分“三同/两同一不同/三不同”枚举印证了原题解中“第 15 题和第 18 题的解法一致”的结论。六、三种解法对比与选型建议维度解法一双指针解法二kSum 递归解法三计数 map源码位置18. 4Sum.go 的fourSum18. 4Sum.go 的fourSum1/kSum/twoSum18. 4Sum.go 的fourSum2时间复杂度O(n³)O(n^(k-1))k4 时为 O(n³)O(m³)m 为去重后元素个数空间复杂度O(n)排序O(k·n)递归路径复制O(n)频次 map去重手段排序 指针跳过重复递归层内跳过重复 值排序频次约束 有序枚举代码通用性仅 4Sum通用 kSum可扩展到任意 k仅 4Sum且依赖频次细分适用场景追求性能与简洁需要解 5Sum、6Sum 等泛化问题值域重复度高、想彻底避免下标重复从仓库测试看三种实现共享同一组用例18. 4Sum_test.go 中fourSum、fourSum1、fourSum2对 9 组输入全部执行可作为交叉验证的基准。七、测试验证用仓库用例确认正确性仓库 18. 4Sum_test.go 覆盖了多类边界场景直接运行即可复现# 在仓库根目录执行 go test ./leetcode/0018.4Sum/ -v -run Test_Problem18测试用例设计亮点输入target期望输出覆盖点[1, 1, 1, 1]4[[1,1,1,1]]四元组全相同需counter 4[1, 0, -1, 0, -2, 2]0三组解题目标准示例[1, 0, -1, 0, -2, 2, 0, 0, 0, 0]0四组解含[0,0,0,0]多个 0 的频次与去重[1, 0, -1, 0, -2, 2, 0, 0, 0, 0]1三组解非零 target[2, 2, 2, 2, 1]8[[2,2,2,2]]尾随重复值 1 不应被误用[1, 1, 3, 4, 5, 5]10[[1,1,3,5]]右指针去重分支右侧 5,5 重复测试中的sameQuads辅助函数将四元组序列化为字符串后做频次差校验忽略顺序地比较两组解集是否完全一致18. 4Sum_test.go这正是对题目“解集不能重复”约束的自动化检验。八、总结4Sum 的三种解法殊途同归解法一用排序保证全局单调、用指针跳跃吃掉重复解法二把去重收敛到“同层跳过相等值”这一条规则换来 kSum 的通用性解法三则用频次 map 把“同一个值用几次”显式建模从源头上消灭下标带来的重复。三者都验证了原题解的核心结论——排序 去重是 N 数之和问题的通用钥匙而 LeetCode-Go 仓库 0018.4Sum 文档 中“第 15 题与第 18 题解法一致”的论断也在 15. 3Sum.go 与本题源码的高度同构中得到了印证。掌握这三套方案你可以轻松迁移到 3Sum、3Sum Closest0016、4Sum-II0454等一系列和问题。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 LeetCode-Go 题解 18. 4Sum：三种去重方案实现四数之和
LeetCode-Go 题解 18. 4Sum三种去重方案实现四数之和【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go本篇文章以 LeetCode-Go 仓库中 0018.4Sum 官方题解 为主线深入剖析 4Sum 问题中“去重”这一核心难点完整还原仓库实现的三种解法双指针、kSum 递归泛化与计数 map 枚举并结合 18. 4Sum.go 源码与 18. 4Sum_test.go 测试用例给出可复现、可验证的实战方案。读完本文你将掌握 N 数之和问题从 2Sum 到 kSum 的完整推导链并理解在 Go 中如何保证解集不重复。一、题目回顾在 n 个整数中寻找和为 target 的四元组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.注意Note解集中不得包含重复的四元组The solution set must not contain duplicate quadruplets。官方给出的示例输入输出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] ]题目大意见 README.md给定一个数组要求在这个数组中找出 4 个数之和为 0 的所有组合。二、核心难点输出解集必须去重4Sum 与 2Sum、3Sum 的最大区别在于去重难度呈指数级上升。原题解0018.4Sum.md 的 “Solution Approach / 解题思路” 一节明确指出数组中同一个数字可能出现多次同一个数字也可能被多次选用但最终输出的解不能重复。例如[-1, 1, 2, -2]、[2, -1, -2, 1]、[-2, 2, -1, 1]属于同一组解即使-1、-2在数组中出现了 100 次、每次使用的下标都不同也不能分别输出因此解题必须同时依赖排序与去重两条手段。三、解法一排序 双指针推荐O(n³)这是仓库中标注为“解法一 双指针”的默认实现对应 18. 4Sum.go也是 3Sum 双指针思路向 4Sum 的自然推广。3.1 核心流程先对数组nums升序排序固定最外层索引i四元组第一个数内层固定索引j第二个数对剩余的区间[j1, n-1]使用left、right双指针相向扫描寻找nums[i] nums[j] nums[left] nums[right] target的组合命中后移动指针并跳过所有相邻的重复值从而保证解不重复。func fourSum(nums []int, target int) (quadruplets [][]int) { sort.Ints(nums) n : len(nums) for i : 0; i n-3 nums[i]nums[i1]nums[i2]nums[i3] target; i { if i 0 nums[i] nums[i-1] || nums[i]nums[n-3]nums[n-2]nums[n-1] target { continue } for j : i 1; j n-2 nums[i]nums[j]nums[j1]nums[j2] target; j { if j i1 nums[j] nums[j-1] || nums[i]nums[j]nums[n-2]nums[n-1] target { continue } for left, right : j1, n-1; left right; { if sum : nums[i] nums[j] nums[left] nums[right]; sum target { quadruplets append(quadruplets, []int{nums[i], nums[j], nums[left], nums[right]}) for left; left right nums[left] nums[left-1]; left { } for right--; left right nums[right] nums[right1]; right-- { } } else if sum target { left } else { right-- } } } } return }3.2 去重与剪枝细节解读这段代码在可读性之外隐藏了三个对性能影响巨大的细节逐个拆解1外层i的去重与“最小可达值”剪枝for i : 0; i n-3 nums[i]nums[i1]nums[i2]nums[i3] target; i {i n-3保证i后面至少还能取 3 个数nums[i]nums[i1]nums[i2]nums[i3] target前四个最小数的和已经大于 target说明以当前i及之后任意位置开头的四元组都不可能再等于 target直接终止外层循环剪枝。if i 0 nums[i] nums[i-1] || nums[i]nums[n-3]nums[n-2]nums[n-1] target { continue }i 0 nums[i] nums[i-1]跳过与上一个相同的固定值避免产生重复四元组nums[i]nums[n-3]nums[n-2]nums[n-1] target当前i与数组最大的三个数相加仍小于 target说明i太小无论如何组合都不可能达到 target直接跳过注意这里用了短路||会先判去重再判剪枝。2内层j的对称去重与剪枝for j : i 1; j n-2 nums[i]nums[j]nums[j1]nums[j2] target; j {j n-2保证j后面还能取 2 个数nums[i]nums[j]nums[j1]nums[j2] target固定i, j后能取到的最小两数和若已超过剩余额度则终止内层循环。if j i1 nums[j] nums[j-1] || nums[i]nums[j]nums[n-2]nums[n-1] target { continue }j i1 nums[j] nums[j-1]跳过重复的第二个固定值nums[i]nums[j]nums[n-2]nums[n-1] target固定i, j后与最大的两个数相加仍小于 target说明j太小跳过。3双指针区间的双重去重命中sum target后for left; left right nums[left] nums[left-1]; left { } for right--; left right nums[right] nums[right1]; right-- { }先移动指针再跳过所有与刚选中值相同的元素——左右两侧各自吃掉连续重复段。测试用例中特意加入了{1, 1, 3, 4, 5, 5}, 10这类**右端存在重复值5, 5**的输入用于覆盖右指针nums[right] nums[right1]的去重分支见 18. 4Sum_test.go 的注释。当sum target时left当sum target时right--利用排序数组的单向移动性保证每个合法组合至多被枚举一次。3.3 复杂度时间复杂度O(n³)。外层两重循环嵌套双指针线性扫描空间复杂度O(n)排序所需空间忽略输出。该复杂度标注与仓库 Two_Pointers 分类表 中对 0018 的记录一致表中标注 O(n³) / O(n)。四、解法二kSum 递归泛化一码通吃 k 数之和仓库中“解法二 kSum”将 4Sum 抽象成通用的 kSum 递归框架18. 4Sum.go当k 2时退化为经典双指针 twoSum。4.1 入口与递归框架func fourSum1(nums []int, target int) [][]int { res, cur : make([][]int, 0), make([]int, 0) sort.Ints(nums) kSum(nums, 0, len(nums)-1, target, 4, cur, res) return res } func kSum(nums []int, left, right int, target int, k int, cur []int, res *[][]int) { if right-left1 k || k 2 || target nums[left]*k || target nums[right]*k { return } if k 2 { // 2 sum twoSum(nums, left, right, target, cur, res) } else { for i : left; i len(nums); i { if i left || (i left nums[i-1] ! nums[i]) { next : make([]int, len(cur)) copy(next, cur) next append(next, nums[i]) kSum(nums, i1, len(nums)-1, target-nums[i], k-1, next, res) } } } }4.2 三个关键设计剪枝条件进入递归前一次性判断if right-left1 k || k 2 || target nums[left]*k || target nums[right]*k { return }right-left1 k剩余区间元素个数不足 k 个k 2递归底线target nums[left]*k区间最小 k 个数的和已超过 targettarget nums[right]*k区间最大 k 个数的和仍不足 target。去重策略在for i : left; i len(nums); i中只有i left或nums[i-1] ! nums[i]时才进入下一层即同一层跳过重复的固定元素这是保证全局解不重复的核心。路径传递cur切片通过copy复制后追加当前选中的数再传入下一层避免递归回溯时共享底层数组导致结果互相污染res使用*[][]int指针在所有递归层之间共享收集结果。4.3 底层的 twoSumfunc twoSum(nums []int, left, right int, target int, cur []int, res *[][]int) { for left right { sum : nums[left] nums[right] if sum target { cur append(cur, nums[left], nums[right]) temp : make([]int, len(cur)) copy(temp, cur) *res append(*res, temp) // reset cur to previous state cur cur[:len(cur)-2] left right-- for left right nums[left] nums[left-1] { left } for left right nums[right] nums[right1] { right-- } } else if sum target { left } else { right-- } } }命中后先copy一份快照写入res再将cur通过cur cur[:len(cur)-2]回退到进入前的状态代码注释明确标注了// reset cur to previous state保证上层递归继续遍历时路径状态正确。五、解法三计数 map 排序去重面向去重设计的枚举仓库中“解法三”采用先统计频次、再按去重后的值枚举的思路18. 4Sum.go这也是原题解在“Solution Approach”中描述的核心思路Use a map to precompute and store the sums of any 3 numbers, which can reduce the time complexity to O(n³). ... map 记录每个数字出现的次数然后对 map 的 key 数组进行排序最后在这个排序以后的数组里面扫找到另外 3 个数字能和自己组成 0 的组合。5.1 预处理频次统计 key 排序counter : map[int]int{} for _, value : range nums { counter[value] } uniqNums : []int{} for key : range counter { uniqNums append(uniqNums, key) } sort.Ints(uniqNums)先统计每个数值出现次数再取所有不同的 key 排序。之后所有枚举都基于去重后的uniqNums天然杜绝了因相同数值不同下标产生的重复解。5.2 分情况枚举四元组的五种“频次形态”因为四元组中可能包含重复值代码按重复形态分类处理1四个相同x*4 target且counter[x] 4if (uniqNums[i]*4 target) counter[uniqNums[i]] 4 { res append(res, []int{uniqNums[i], uniqNums[i], uniqNums[i], uniqNums[i]}) }2三个相同 一个不同两类x*3y target要求counter[x] 2if (uniqNums[i]*3uniqNums[j] target) counter[uniqNums[i]] 2 { res append(res, []int{uniqNums[i], uniqNums[i], uniqNums[i], uniqNums[j]}) } if (uniqNums[j]*3uniqNums[i] target) counter[uniqNums[j]] 2 { res append(res, []int{uniqNums[i], uniqNums[j], uniqNums[j], uniqNums[j]}) }3两两相同x*2y*2 target要求两个数的频次都 1if (uniqNums[j]*2uniqNums[i]*2 target) counter[uniqNums[j]] 1 counter[uniqNums[i]] 1 { res append(res, []int{uniqNums[i], uniqNums[i], uniqNums[j], uniqNums[j]}) }4两个相同 两个不同三类形如x,x,y,z要求counter[x] 1if (uniqNums[i]*2uniqNums[j]uniqNums[k] target) counter[uniqNums[i]] 1 { res append(res, []int{uniqNums[i], uniqNums[i], uniqNums[j], uniqNums[k]}) } if (uniqNums[j]*2uniqNums[i]uniqNums[k] target) counter[uniqNums[j]] 1 { res append(res, []int{uniqNums[i], uniqNums[j], uniqNums[j], uniqNums[k]}) } if (uniqNums[k]*2uniqNums[i]uniqNums[j] target) counter[uniqNums[k]] 1 { res append(res, []int{uniqNums[i], uniqNums[j], uniqNums[k], uniqNums[k]}) }5四个互不相同三数确定后反推第四个c : target - uniqNums[i] - uniqNums[j] - uniqNums[k] if c uniqNums[k] counter[c] 0 { res append(res, []int{uniqNums[i], uniqNums[j], uniqNums[k], c}) }注意这里用c uniqNums[k]约束第四个数必须严格大于第三个数从而保证(i, j, k, c)组合的枚举顺序唯一、互不重复——这是比单纯查频次更精妙的一层去重。该解法在去重思想上与仓库中 3Sum 的“解法二”完全同构对比 15. 3Sum.go同样统计频次、排序 key、分“三同/两同一不同/三不同”枚举印证了原题解中“第 15 题和第 18 题的解法一致”的结论。六、三种解法对比与选型建议维度解法一双指针解法二kSum 递归解法三计数 map源码位置18. 4Sum.go 的fourSum18. 4Sum.go 的fourSum1/kSum/twoSum18. 4Sum.go 的fourSum2时间复杂度O(n³)O(n^(k-1))k4 时为 O(n³)O(m³)m 为去重后元素个数空间复杂度O(n)排序O(k·n)递归路径复制O(n)频次 map去重手段排序 指针跳过重复递归层内跳过重复 值排序频次约束 有序枚举代码通用性仅 4Sum通用 kSum可扩展到任意 k仅 4Sum且依赖频次细分适用场景追求性能与简洁需要解 5Sum、6Sum 等泛化问题值域重复度高、想彻底避免下标重复从仓库测试看三种实现共享同一组用例18. 4Sum_test.go 中fourSum、fourSum1、fourSum2对 9 组输入全部执行可作为交叉验证的基准。七、测试验证用仓库用例确认正确性仓库 18. 4Sum_test.go 覆盖了多类边界场景直接运行即可复现# 在仓库根目录执行 go test ./leetcode/0018.4Sum/ -v -run Test_Problem18测试用例设计亮点输入target期望输出覆盖点[1, 1, 1, 1]4[[1,1,1,1]]四元组全相同需counter 4[1, 0, -1, 0, -2, 2]0三组解题目标准示例[1, 0, -1, 0, -2, 2, 0, 0, 0, 0]0四组解含[0,0,0,0]多个 0 的频次与去重[1, 0, -1, 0, -2, 2, 0, 0, 0, 0]1三组解非零 target[2, 2, 2, 2, 1]8[[2,2,2,2]]尾随重复值 1 不应被误用[1, 1, 3, 4, 5, 5]10[[1,1,3,5]]右指针去重分支右侧 5,5 重复测试中的sameQuads辅助函数将四元组序列化为字符串后做频次差校验忽略顺序地比较两组解集是否完全一致18. 4Sum_test.go这正是对题目“解集不能重复”约束的自动化检验。八、总结4Sum 的三种解法殊途同归解法一用排序保证全局单调、用指针跳跃吃掉重复解法二把去重收敛到“同层跳过相等值”这一条规则换来 kSum 的通用性解法三则用频次 map 把“同一个值用几次”显式建模从源头上消灭下标带来的重复。三者都验证了原题解的核心结论——排序 去重是 N 数之和问题的通用钥匙而 LeetCode-Go 仓库 0018.4Sum 文档 中“第 15 题与第 18 题解法一致”的论断也在 15. 3Sum.go 与本题源码的高度同构中得到了印证。掌握这三套方案你可以轻松迁移到 3Sum、3Sum Closest0016、4Sum-II0454等一系列和问题。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考