LeetCode 4Sum（四數之和）

一、題目描述

給定數組 nums 和目標值 target，找出所有不重複的四元組 [a,b,c,d] 使 a+b+c+d = target。四元組內非遞減，結果集去重。

二、解題思路：哈希表優化 (兩數之和拆解)

將四數拆為兩組兩數之和：
1. 遍歷所有數對 (i,j)，計算和 sum = nums[i]+nums[j]，存入哈希表 map>>。
2. 再次遍歷數對 (i,j)，查找 target - (nums[i]+nums[j]) 是否在表中。
3. 為避免重複，要求第二組數對的起始索引 > 第一組的結束索引 j。
4. 將找到的四元組排序後存入 set 去重，最後轉為列表。

三、代碼實現（Python）

class Solution(object):
    def fourSum(self, nums, target):
        if len(nums) < 4: return []
        result = set()
        sum_pairs = {}
        for i in range(len(nums)):
            for j in range(i+1, len(nums)):
                s = nums[i] + nums[j]
                if s in sum_pairs:
                    sum_pairs[s].append((i,j))
                else:
                    sum_pairs[s] = [(i,j)]
        for i in range(len(nums)):
            for j in range(i+1, len(nums)):
                need = target - (nums[i] + nums[j])
                if need in sum_pairs:
                    for (k,l) in sum_pairs[need]:
                        if k > j:  # 保證索引不重疊、順序
                            quad = tuple(sorted([nums[i], nums[j], nums[k], nums[l]]))
                            result.add(quad)
        return [list(q) for q in result]

# 測試
if __name__ == "__main__":
    assert Solution().fourSum([1,0,-1,0,-2,2], 0) == [[-1,0,0,1],[-2,0,0,2],[-2,-1,1,2]]

四、複雜度分析

• 時間：O(n²) 平均（哈希表查找 O(1)）
• 空間：O(n²) 存儲數對和

此法將 4Sum 轉化為兩次 2Sum，利用哈希表優化，比雙指針排序法（O(n³)）更快。