如何优化判断两数组元素配对和为目标值的Python代码？

Your current brute-force implementation works correctly for small arrays, but it doesn't scale well when dealing with larger datasets. Let's break down why, and then look at a much more efficient approach.

The Problem with the Original Code #

Your double-loop approach has a time complexity of O(n*m), where n is the length of array a and m is the length of array b. For example, if both arrays have 10,000 elements, that's 100 million operations—way too slow for real-world use cases.

A Faster Approach Using Sets #

The key optimization here is leveraging hash set lookups, which have an average time complexity of O(1). Here's how it works:

• Convert one of the arrays into a set (we'll pick the smaller one to save space).
• Iterate through the other array, and for each element x, check if v - x exists in the set. If it does, we've found our pair.

This reduces the time complexity to O(n + m)—a massive improvement for large arrays.

Optimized Code Implementation #

def sumOfTwo(a, b, v):
    # Convert the smaller array to a set to minimize space usage
    smaller_set = set(a) if len(a) <= len(b) else set(b)
    larger_list = b if len(a) <= len(b) else a
    
    for num in larger_list:
        complement = v - num
        if complement in smaller_set:
            return True
    return False

Why This Works #

Let's test it with your example:

• a = [1, 2, 3], b = [10, 20, 30, 40], v = 42
• We convert a to a set {1, 2, 3} (since it's smaller)
• Iterate through b: when we hit 40, 42 - 40 = 2, which is in the set—so we return True immediately.

Edge Cases Handled #

• If either array is empty: the loop will never find a complement, so we return False correctly.
• Duplicate values in the arrays: sets handle duplicates automatically, but since we only care about existence, this doesn't affect the result.

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