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 核心流程

1. 先对数组nums升序排序；
2. 固定最外层索引i（四元组第一个数），内层固定索引j（第二个数）；
3. 对剩余的区间[j+1, n-1]使用left、right双指针相向扫描，寻找nums[i] + nums[j] + nums[left] + nums[right] == target的组合；
4. 命中后移动指针并跳过所有相邻的重复值，从而保证解不重复。

func fourSum(nums []int, target int) (quadruplets [][]int) { sort.Ints(nums) n := len(nums) for i := 0; i < n-3 && nums[i]+nums[i+1]+nums[i+2]+nums[i+3] <= 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[j+1]+nums[j+2] <= target; j++ { if j > i+1 && nums[j] == nums[j-1] || nums[i]+nums[j]+nums[n-2]+nums[n-1] < target { continue } for left, right := j+1, 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[right+1]; right-- { } } else if sum < target { left++ } else { right-- } } } } return }

3.2 去重与剪枝细节解读

这段代码在可读性之外隐藏了三个对性能影响巨大的细节，逐个拆解：

（1）外层i的去重与“最小可达值”剪枝

for i := 0; i < n-3 && nums[i]+nums[i+1]+nums[i+2]+nums[i+3] <= target; i++ {

• i < n-3：保证i后面至少还能取 3 个数；
• nums[i]+nums[i+1]+nums[i+2]+nums[i+3] <= 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[j+1]+nums[j+2] <= target; j++ {

• j < n-2保证j后面还能取 2 个数；
• nums[i]+nums[j]+nums[j+1]+nums[j+2] <= target：固定i, j后，能取到的最小两数和若已超过剩余额度，则终止内层循环。

if j > i+1 && nums[j] == nums[j-1] || nums[i]+nums[j]+nums[n-2]+nums[n-1] < target { continue }

• j > i+1 && 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[right+1]; right-- { }

先移动指针，再跳过所有与刚选中值相同的元素——左右两侧各自吃掉连续重复段。测试用例中特意加入了{1, 1, 3, 4, 5, 5}, 10这类**右端存在重复值（5, 5）**的输入，用于覆盖右指针nums[right] == nums[right+1]的去重分支（见 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-left+1 < 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, i+1, len(nums)-1, target-nums[i], k-1, next, res) } } } }

4.2 三个关键设计

剪枝条件（进入递归前一次性判断）：

if right-left+1 < k || k < 2 || target < nums[left]*k || target > nums[right]*k { return }

• right-left+1 < k：剩余区间元素个数不足 k 个；
• k < 2：递归底线；
• target < nums[left]*k：区间最小 k 个数的和已超过 target；
• target > 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 底层的 twoSum

func 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[right+1] { 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] >= 4

if (uniqNums[i]*4 == target) && counter[uniqNums[i]] >= 4 { res = append(res, []int{uniqNums[i], uniqNums[i], uniqNums[i], uniqNums[i]}) }

（2）三个相同 + 一个不同（两类）：x*3+y == target，要求counter[x] > 2

if (uniqNums[i]*3+uniqNums[j] == target) && counter[uniqNums[i]] > 2 { res = append(res, []int{uniqNums[i], uniqNums[i], uniqNums[i], uniqNums[j]}) } if (uniqNums[j]*3+uniqNums[i] == target) && counter[uniqNums[j]] > 2 { res = append(res, []int{uniqNums[i], uniqNums[j], uniqNums[j], uniqNums[j]}) }

（3）两两相同：x*2+y*2 == target，要求两个数的频次都> 1

if (uniqNums[j]*2+uniqNums[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] > 1

if (uniqNums[i]*2+uniqNums[j]+uniqNums[k] == target) && counter[uniqNums[i]] > 1 { res = append(res, []int{uniqNums[i], uniqNums[i], uniqNums[j], uniqNums[k]}) } if (uniqNums[j]*2+uniqNums[i]+uniqNums[k] == target) && counter[uniqNums[j]] > 1 { res = append(res, []int{uniqNums[i], uniqNums[j], uniqNums[j], uniqNums[k]}) } if (uniqNums[k]*2+uniqNums[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 题的解法一致”的结论。

六、三种解法对比与选型建议

从仓库测试看，三种实现共享同一组用例（18. 4Sum_test.go 中fourSum、fourSum1、fourSum2对 9 组输入全部执行），可作为交叉验证的基准。

七、测试验证：用仓库用例确认正确性

仓库 18. 4Sum_test.go 覆盖了多类边界场景，直接运行即可复现：

# 在仓库根目录执行 go test ./leetcode/0018.4Sum/ -v -run Test_Problem18

测试用例设计亮点：

测试中的sameQuads辅助函数将四元组序列化为字符串后做频次差校验，忽略顺序地比较两组解集是否完全一致（18. 4Sum_test.go），这正是对题目“解集不能重复”约束的自动化检验。

八、总结

4Sum 的三种解法殊途同归：解法一用排序保证全局单调、用指针跳跃吃掉重复；解法二把去重收敛到“同层跳过相等值”这一条规则，换来 kSum 的通用性；解法三则用频次 map 把“同一个值用几次”显式建模，从源头上消灭下标带来的重复。三者都验证了原题解的核心结论——排序 + 去重是 N 数之和问题的通用钥匙，而 LeetCode-Go 仓库 0018.4Sum 文档 中“第 15 题与第 18 题解法一致”的论断，也在 15. 3Sum.go 与本题源码的高度同构中得到了印证。掌握这三套方案，你可以轻松迁移到 3Sum、3Sum Closest（0016）、4Sum-II（0454）等一系列和问题。

【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go