LeetCode 3Sum问题Python解法超时优化请求

原代码问题分析 #

原代码超时的核心原因在于以下几点：

• 每次调用search都复制整个数组，带来O(n)的额外时间开销，循环n次后累计O(n²)的冗余操作。
• 使用if n not in sol判断重复解，这是O(m)的线性查找（m为当前解的数量），最坏情况下会导致O(n³)的时间复杂度。
• search函数中使用pop修改数组，不仅会打乱索引逻辑，而且列表的pop操作（尤其是中间元素）本身是O(n)复杂度，进一步拖慢速度。

修改后的代码 #

def threeSum(nums):
    sol = []
    nums.sort()
    n = len(nums)
    
    for i in range(n - 2):
        # 跳过重复的固定元素，避免生成重复解
        if i > 0 and nums[i] == nums[i-1]:
            continue
        # 双指针初始化
        l, r = i + 1, n - 1
        while l < r:
            total = nums[i] + nums[l] + nums[r]
            if total == 0:
                sol.append([nums[i], nums[l], nums[r]])
                # 跳过左指针重复元素
                while l < r and nums[l] == nums[l+1]:
                    l += 1
                # 跳过右指针重复元素
                while l < r and nums[r] == nums[r-1]:
                    r -= 1
                # 移动指针寻找下一组可能解
                l += 1
                r -= 1
            elif total < 0:
                l += 1
            else:
                r -= 1
    return sol

时间复杂度分析 #

原代码时间复杂度 #

• 外层循环遍历O(n)次，每次调用search时复制数组O(n)，search内部双指针循环最多O(n)次，再加上每次判断n not in sol的O(m)（m最多O(n²)），最坏情况下时间复杂度为O(n³)，这也是导致超时的根本原因。

新代码时间复杂度 #

• 排序数组的时间为O(n log n)。
• 外层循环遍历O(n)次，每次内层双指针循环最多O(n)次，且所有跳过重复元素的操作都是O(1)的判断，因此整体时间复杂度为O(n²)，完全符合LeetCode的时间要求，可以通过所有测试用例。

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