如何用哈希表/字典消除LeetCode 4Sum中的重复四元组？

失败原因 #

你的哈希表解法在nums = [2,2,2,2,2]、target=8测试用例中失败，核心问题是未处理索引顺序约束与重复四元组：

• 原实现中，你可能直接存储了所有两元素组合的和，但未限制后续匹配的数对索引必须在前一个数对的索引之后。比如，匹配(0,1)的和4与(2,3)的和4时会得到有效四元组，但同时也会匹配(0,2)的和4与(1,3)的和4，这同样得到[2,2,2,2]，导致结果中出现大量重复的四元组。
• 此外，若未对数组排序，相同元素的不同索引组合会被当成不同的数对存储，进一步加剧重复问题，而题目要求返回的四元组必须是唯一的。

修改方案（保留O(n²)时间、O(n)空间复杂度） #

我们可以通过排序数组+索引顺序约束+重复元素跳过来解决问题，具体步骤如下：

1. 先对数组排序 #

排序后相同元素会相邻，便于后续跳过重复元素，同时保证生成的四元组是有序的，避免因元素顺序不同导致的重复。

2. 构建哈希表存储两数对及其索引 #

遍历所有i < j的数对，计算两数之和作为键，值为该和对应的索引对(i,j)列表。同时，跳过重复的数对（当nums[i] == nums[i-1]且i > 0时跳过当前i；当nums[j] == nums[j-1]且j > i+1时跳过当前j），减少哈希表中的冗余数据。

3. 二次遍历数对并匹配补数 #

再次遍历所有k < l的数对，计算需要的补数target - (nums[k]+nums[l])。若补数存在于哈希表中，遍历对应的索引对(i,j)，仅保留j < k的组合（保证四个索引i < j < k < l，避免元素重复使用与四元组重复）。同样，遍历k和l时跳过重复元素，进一步避免生成重复四元组。

示例代码 #

def fourSum(nums, target):
    nums.sort()
    n = len(nums)
    pair_sum = {}
    result = set()
    
    # 第一步：存储所有i<j的数对及索引
    for i in range(n):
        # 跳过重复的i
        if i > 0 and nums[i] == nums[i-1]:
            continue
        for j in range(i+1, n):
            # 跳过重复的j（相对于当前i）
            if j > i+1 and nums[j] == nums[j-1]:
                continue
            s = nums[i] + nums[j]
            if s not in pair_sum:
                pair_sum[s] = []
            pair_sum[s].append((i, j))
    
    # 第二步：遍历k<l的数对，匹配补数
    for k in range(n):
        # 跳过重复的k
        if k > 0 and nums[k] == nums[k-1]:
            continue
        for l in range(k+1, n):
            # 跳过重复的l（相对于当前k）
            if l > k+1 and nums[l] == nums[l-1]:
                continue
            s = nums[k] + nums[l]
            complement = target - s
            if complement in pair_sum:
                for (i, j) in pair_sum[complement]:
                    # 保证j < k，避免索引重叠与重复组合
                    if j < k:
                        quad = (nums[i], nums[j], nums[k], nums[l])
                        result.add(quad)
    
    return list(result)

方案说明 #

• 时间复杂度：两次双重循环均为O(n²)，哈希表的查询和插入操作是平均O(1)，整体平均时间复杂度为O(n²)。
• 空间复杂度：哈希表存储最多O(n²)个数对，但通过跳过重复元素，实际空间接近O(n)（当数组元素重复较多时）；结果集存储唯一四元组，空间复杂度为O(1)（不计结果存储），符合你的需求。

内容的提问来源于stack exchange，提问作者Thonky456