【LeetCode】18. 四数之和

18. 四数之和

题目描述

给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：

• 0 <= a, b, c, d < n
• a、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 递归框架：当 k==2 时用双指针解决，否则固定一个元素，递归解决 (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从i+1到n-3]D --> E{去重/剪枝}E -->|不满足| DE --> F[left=j+1,right=n-1]F --> G{left<right?}G -->|否| DG --> H[sum=nums[i]+nums[j]+nums[left]+nums[right]]H --> I{sum==target?}I -->|是| J[加入解并去重移动]I -->|sum<target| K[left++]I -->|sum>target| L[right--]J --> GK --> GL --> G

算法二：通用 kSum（含 2Sum 双指针）

• 排序
• kSum(nums,k,start,target):
  • 若 k==2，用双指针在区间 [start,n) 里求两数和为 target 的所有解
  • 否则，从 start 枚举 i，跳过重复元素，并递归 kSum(nums,k-1,i+1,target-nums[i])
• 结合最小/最大可能和剪枝

flowchart TDA[sort(nums)] --> B[kSum(nums,4,0,target)]B --> C{k==2?}C -->|是| D[2Sum 双指针]C -->|否| E[for i from start to n-k]E --> F{跳过重复}F --> EE --> G[递归 kSum(k-1,i+1,target-nums[i])]G --> H[前缀拼接nums[i]并收集]H --> E

复杂度

• 排序 + 双指针：时间 O(n^3)，空间 O(1)（不计结果集）
• kSum：最坏也为 O(n^{k-1})，本题 k=4 即 O(n^3)

关键细节

• 去重：
  • i>0 且 nums[i]==nums[i-1] 跳过
  • j>i+1 且 nums[j]==nums[j-1] 跳过
  • 命中答案后 left/right 向内移动并跳过相同值
• 剪枝：
  • 对当前固定前缀，比较最小可能和与最大可能和与 target 的关系进行 break/continue
• long 溢出处理：
  • 计算和时转为 int64 避免大数相加溢出

代码实现要点

1. 先排序，明确单调结构便于双指针
2. 严格实现四处去重逻辑，保证不重复
3. 使用 int64 做加法再比较，避免溢出
4. 通过下界/上界剪枝减少无效搜索

本仓库 18/main.go 中提供：

• fourSum：排序 + 双指针实现
• fourSumKSum + kSum：通用 kSum 版本
• 主函数内含示例用例并输出结果，便于自检

完整题解代码

package mainimport ("fmt""sort"
)// 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[i+1]) + int64(nums[i+2]) + int64(nums[i+3])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 > i+1 && nums[j] == nums[j-1] {continue}// 剪枝min2 := int64(nums[i]) + int64(nums[j]) + int64(nums[j+1]) + int64(nums[j+2])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 := j+1, 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 k=4）
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 start+i >= n {return res}minSum += int64(nums[start+i])}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, i+1, 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))
}