LeetCode 3Sum算法超时问题求助：大输入场景下的优化建议

Hey there! It sounds like your current 3Sum implementation is hitting efficiency walls with larger input datasets—and that’s totally expected if you’re using a brute-force or unoptimized approach. Let’s break down why you’re seeing TLE (Time Limit Exceeded) and walk through the standard optimized solution for this problem.

Why Your Current Approach Is Timing Out #

The most common culprits for 3Sum TLE are:

• Brute-force triple loops: A naive O(n³) approach where you check every possible triplet will absolutely fail for arrays with even a few thousand elements—10,000 elements would mean 1 trillion operations, which is way too slow.
• Unoptimized two-loop + hash map: While this cuts time to O(n²), not handling duplicate values properly leads to redundant calculations and extra work that adds up for large inputs.
• No early termination: Not stopping the loop when it’s impossible to form a valid triplet (e.g., when the first element is positive, since all subsequent elements are larger and can’t sum to zero).

The Optimized Solution: Sort + Two Pointers #

The industry-standard approach for 3Sum runs in O(n²) time (with O(log n) for sorting) and efficiently avoids duplicates. Here’s how it works:

Step-by-Step Breakdown #

1. Sort the array first: Sorting lets us use two pointers to find pairs quickly, and makes skipping duplicate values trivial.
2. Fix the first element: Iterate through each element as the first value (a) in the triplet (a, b, c).
3. Use two pointers for the remaining pair: For each fixed a, set a left pointer at the next element and a right pointer at the end of the array. Adjust the pointers based on whether a + b + c is less than, greater than, or equal to 0.
4. Skip duplicates: Avoid processing the same value multiple times for a, b, or c to prevent duplicate triplets and reduce unnecessary computations.

Example Code (Python) #

def threeSum(nums):
    nums.sort()
    triplets = []
    n = len(nums)
    
    for i in range(n):
        # Skip duplicate first elements to avoid duplicate triplets
        if i > 0 and nums[i] == nums[i-1]:
            continue
        # Early exit: if first element is positive, no way to get sum 0
        if nums[i] > 0:
            break
        
        left = i + 1
        right = n - 1
        while left < right:
            current_sum = nums[i] + nums[left] + nums[right]
            
            if current_sum < 0:
                # Need a larger sum: move left pointer right
                left += 1
            elif current_sum > 0:
                # Need a smaller sum: move right pointer left
                right -= 1
            else:
                # Found a valid triplet
                triplets.append([nums[i], nums[left], nums[right]])
                # Skip duplicate left values
                while left < right and nums[left] == nums[left + 1]:
                    left += 1
                # Skip duplicate right values
                while left < right and nums[right] == nums[right - 1]:
                    right -= 1
                # Move pointers to look for next possible pair
                left += 1
                right -= 1
    
    return triplets

Key Optimizations Explained #

• Early termination: Once nums[i] is positive, all subsequent elements are also positive (since the array is sorted), so their sum can never be zero. We break the loop immediately here.
• Duplicate skipping: By checking if the current element is the same as the previous one, we avoid reprocessing the same value and generating duplicate triplets. This cuts down on a lot of redundant work.
• Two-pointer efficiency: Instead of nested loops to find b and c, the two-pointer approach lets us find valid pairs in linear time for each fixed a, bringing the overall complexity to O(n²)—fast enough for even large input sizes like the one you’re working with.

Give this approach a try—it should handle your large input without hitting time limits!

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