Testdome Python的Two Sum测试：性能测试报Wrong answer如何解决？

Hey there! It’s super frustrating when code works for small test cases but fails on large ones—especially when it’s a "Wrong answer" instead of a timeout. That means the issue is a logical bug that only surfaces with bigger datasets, not just a speed problem. Let’s break down the most likely culprits and fix them:

Common Logical Bugs That Fail Large Datasets #

• Accidentally using the same element twice
  If your code checks for a complement in a hash map before making sure the stored index isn’t the same as the current one, you’ll hit this issue when target_sum is exactly twice a value in the list. For example, numbers = [2, 4] with target_sum = 4 would incorrectly return (0, 0) instead of (-1, -1).

• Overwriting duplicate value indices
  Suppose you have numbers = [3, 3] and target_sum = 6. If you first add each value to the hash map and then check for the complement, you’ll overwrite the first 3’s index with the second. When you check the second 3, you’ll only find the same index in the map and return (-1, -1) instead of the valid (0, 1).

• Incorrect handling of negative numbers
  Large datasets often include negative values, and if your code has implicit assumptions (like "values are positive"), it’ll miss valid pairs. For example, numbers = [-5, -3] with target_sum = -8 requires finding the complement -3 for -5—if your hash map doesn’t support negative keys, or you skip negative values, this pair will be missed.

• Returning invalid index pairs
  Some implementations accidentally return indices out of bounds, or pairs where the elements don’t actually sum to target_sum—a bug that might not show up in small tests but gets amplified in large datasets with more edge cases.

Fix: Correct Hash Map Implementation #

The standard O(n) solution avoids these issues by checking for the complement before adding the current value to the map. Here’s a Python example that handles all edge cases:

def two_sum(numbers, target_sum):
    num_to_index = {}
    for idx, num in enumerate(numbers):
        complement = target_sum - num
        # Check if we've already seen the complement (and it's not the same element)
        if complement in num_to_index:
            return (num_to_index[complement], idx)
        # Add current number and index to the map AFTER checking
        num_to_index[num] = idx
    # No valid pair found
    return (-1, -1)

Why This Works: #

1. It ensures we never use the same element twice—since we check for the complement before storing the current index.
2. Duplicate values are handled correctly: the first occurrence of a value is stored, so when a duplicate comes in, its complement (the first occurrence) is already in the map.
3. Negative numbers are supported natively by the hash map, no extra logic needed.
4. It returns the first valid pair found, which meets the problem’s requirement of returning any valid pair.

Quick Checks to Verify Your Code #

• Double-check that you’re returning a tuple (-1, -1) (not a list or other type) when no pair exists—some test platforms are strict about return types.
• Ensure your loop runs through all elements (from index 0 to len(numbers)-1), no off-by-one errors.
• Test with edge cases manually: duplicate values, negative sums, large datasets with only one valid pair buried deep.

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