如何优化LeetCode 3Sum解法以解决超时问题？

原解法问题分析 #

你写的三重循环解法逻辑上能找到所有符合条件的三元组，但时间复杂度太高是超时的核心原因。三重嵌套循环的时间复杂度为O(n³)，当输入规模n较大时（比如LeetCode测试用例里n可达10^4级别），计算量会呈立方级爆炸式增长，直接超出时间限制。另外，你用x not in triplet_array做去重判断时，每次都要遍历整个结果数组，又额外增加了不必要的时间开销，进一步拖慢了运行速度。

时空复杂度基础分析 #

• 时间复杂度：指算法运行时间和输入规模的关系。你的三重循环最多会执行n*(n-1)*(n-2)/6次操作，属于O(n³)级别，n越大，耗时增长越快。
• 空间复杂度：指算法运行所需的额外空间。你用到的triplet_array和x，最坏情况下需要存储O(n²)个三元组，空间复杂度为O(n²)。

优化方案：排序+双指针 #

优化核心是把时间复杂度降到O(n²)，具体步骤如下：

1. 先排序数组：排序后既能方便跳过重复元素，也能利用双指针快速定位目标值。
2. 固定第一个元素，双指针找另外两个元素：遍历每个元素作为三元组的第一个数，左指针指向它的下一个位置，右指针指向数组末尾，通过调整指针位置寻找和为0的组合。
3. 跳过重复元素：不管是第一个元素还是双指针移动时，遇到和前一个相同的元素直接跳过，避免生成重复的三元组。

优化后的Python代码 #

class Solution(object):
    def threeSum(self, nums):
        triplet_array = []
        nums.sort()
        n = len(nums)
        
        for i in range(n):
            # 第一个元素大于0，后面都是正数，不可能凑出和为0的三元组，直接终止循环
            if nums[i] > 0:
                break
            # 跳过重复的第一个元素
            if i > 0 and nums[i] == nums[i-1]:
                continue
            # 初始化双指针
            left = i + 1
            right = n - 1
            while left < right:
                current_sum = nums[i] + nums[left] + nums[right]
                if current_sum == 0:
                    triplet_array.append([nums[i], nums[left], nums[right]])
                    # 跳过左指针重复元素
                    while left < right and nums[left] == nums[left+1]:
                        left += 1
                    # 跳过右指针重复元素
                    while left < right and nums[right] == nums[right-1]:
                        right -= 1
                    # 移动指针寻找下一组符合条件的元素
                    left += 1
                    right -= 1
                elif current_sum < 0:
                    # 和太小，左指针右移增大数值
                    left += 1
                else:
                    # 和太大，右指针左移减小数值
                    right -= 1
        return triplet_array

优化后的时空复杂度 #

• 时间复杂度：排序的时间是O(n log n)，遍历第一个元素是O(n)，每个遍历过程中双指针操作是O(n)，总时间复杂度为O(n log n + n²)，最终简化为O(n²)，远低于原解法的O(n³)，能轻松应对大规模输入。
• 空间复杂度：Python的sort是原地排序，额外空间主要用于存储结果数组，最坏情况为O(n²)；如果考虑排序的递归栈空间，为O(log n)，整体空间复杂度由结果数组决定，实际测试中远小于O(n²)。

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