LeetCode 3Sum算法超时疑问：时间复杂度与二分查找正确性排查

Hey there! Let's break down why your code is timing out specifically on the all-zero test case, even though other cases work fine. I'll also check your binary search logic and time complexity claims.

核心超时原因：冗余的重复三元组生成 #

Your biggest issue is how you handle the binary search when you find the target value. Let's take the all-zero array example:

• When nums[i] and nums[j] are both 0, the target becomes 0.
• In your binary search loop, once you find nums[M] == target, you add the triplet to ans but don't break the loop. Instead, you keep moving R = M - 1, which means you'll find every single 0 in the range [j+1, n-1] and add the same [0,0,0] triplet hundreds or thousands of times.

For an array of size 3000 filled with 0s, this generates millions of duplicate triplets in ans. Then your post-processing step (using unordered_set<string> to deduplicate) has to iterate through all these duplicates—this is what's killing your runtime. The sheer volume of data makes the deduplication step take way too long.

二分查找的正确性与冗余 #

Your binary search logic is technically correct for finding the target value, but it's doing unnecessary work. You don't need to find every occurrence of the target—since the array is sorted, any additional occurrences will just create duplicate triplets (since nums[i] and nums[j] are fixed). Finding one occurrence is enough.

优化方案：提前去重 + 终止冗余搜索 #

Here's how to fix your code to eliminate the timeout, while keeping your O(n²logn) time complexity:

1. Skip duplicate values during iteration #

Since the array is sorted, we can skip over duplicate nums[i] and nums[j] before even starting the binary search. This prevents us from generating duplicate triplets in the first place.

2. Break binary search once target is found #

Once you find a valid nums[M] == target, add the triplet and exit the binary search loop immediately—no need to look for more duplicates.

3. Remove post-processing deduplication #

By handling duplicates upfront, you don't need the ans2 and unordered_set<string> steps anymore, which saves a ton of time and memory.

Fixed Code #

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<vector<int>> ans;
        int n = nums.size();
        
        for (int i = 0; i < n - 2; ++i) {
            // Skip duplicate i values
            if (i > 0 && nums[i] == nums[i-1]) continue;
            
            for (int j = i + 1; j < n - 1; ++j) {
                // Skip duplicate j values
                if (j > i + 1 && nums[j] == nums[j-1]) continue;
                
                int target = -(nums[i] + nums[j]);
                int L = j + 1, R = n - 1;
                
                while (L <= R) {
                    int M = L + (R - L) / 2;
                    if (nums[M] == target) {
                        ans.push_back({nums[i], nums[j], nums[M]});
                        break; // Exit once we find a valid triplet
                    } else if (nums[M] < target) {
                        L = M + 1;
                    } else {
                        R = M - 1;
                    }
                }
            }
        }
        return ans;
    }
};

时间复杂度确认 #

Your original claimed time complexity was O(n²logn), but in practice, the all-zero test case made it behave like O(n³) (due to the millions of duplicate triplets). The fixed code maintains the O(n²logn) complexity:

• Sorting the array: O(nlogn)
• Two nested loops: O(n²)
• Binary search inside each loop: O(logn) per iteration

This is efficient enough to pass all LeetCode test cases, including the all-zero one.

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