如何让我的4Sum算法正确运行且时间开销增幅最小？

你的算法漏解的核心原因是索引对存入字典的时机错误：只有当target - rem不在字典中时，才将当前的[i,j]索引对存入字典，导致后续需要和该索引对组合的四元组无法被匹配到。

问题分析 #

以你提供的测试用例为例，当处理四元组[0,2,2,2]时，其中两个2的组合（索引7和8）的和为4，target - 4 = 2，此时字典中存在和为2的索引对（比如0和9），算法会进入匹配分支，但处理完后并未将当前的[7,8]存入字典。虽然这个测试用例中的目标四元组最终可能被其他组合匹配到，但这种逻辑会导致某些场景下的漏解——比如当需要后续索引对与当前索引对组合时，当前索引对未被记录。

修复方案 #

将索引对存入字典的操作从else分支中移出，无论target - rem是否存在于字典中，都执行存入操作。这样能保证所有可能的两数组合都被记录，不会漏掉任何潜在的四元组。

修改后的代码：

def fourSum(self, nums, target):
    """
    :type nums: List[int]
    :type target: int
    :rtype: List[List[int]]
    """
    dic = {}
    ans = set()
    nums.sort()
    for i in range(len(nums) - 1):
        for j in range(i + 1, len(nums)):
            rem = nums[i] + nums[j]
            # 先处理匹配逻辑
            if target - rem in dic:
                for z in dic[target - rem]:
                    if i not in z and j not in z:
                        maybe2 = sorted([nums[i], nums[j], nums[z[0]], nums[z[1]]])
                        ans.add(tuple(maybe2))
            # 无论是否匹配，都将当前索引对存入字典
            if rem in dic:
                dic[rem].append([i, j])
            else:
                dic[rem] = [[i, j]]
    return [list(a) for a in ans]

另外，代码中maybe2的排序可以简化：直接使用sorted([nums[i], nums[j], nums[z[0]], nums[z[1]]])即可，无需调整z的索引顺序，因为排序后结果一致。

时间复杂度说明 #

修改后的算法时间复杂度仍为O(n²)，与原算法一致，仅调整了存入字典的时机，不会大幅增加时间开销，符合你“最小化时间增幅”的要求。

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