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))
}