find two numbers such that they add up to a specific target in Python

Two Sum Problem: Given an array of integers find two numbers such that they add up to a specific target in Python?

To find two numbers in an array that add up to a specific target, you can use several approaches. Here are some efficient methods to solve this problem in Python:

Method 1: Using a Hash Set

This approach involves using a set to track the numbers you’ve seen so far. For each number, you check if the complement (i.e., target - number) is in the set. This method is efficient with a time complexity of $O(n)$ and space complexity of $O(n)$.

def find_two_sum(nums, target):

    seen = set()

    for num in nums:

        complement = target - num

        if complement in seen:

            return (complement, num)

        seen.add(num)

    return None

# Example usage:

nums = [2, 7, 11, 15]

target = 9

print(find_two_sum(nums, target))  # Output: (2, 7)

Method 2: Using a Dictionary

This is similar to the hash set approach but uses a dictionary to store indices of the numbers. It provides an $O(n)$ time complexity and $O(n)$ space complexity.

def find_two_sum(nums, target):

    num_to_index = {}

    for index, num in enumerate(nums):

        complement = target - num

        if complement in num_to_index:

            return (complement, num)

        num_to_index[num] = index

    return None

# Example usage:

nums = [2, 7, 11, 15]

target = 9

print(find_two_sum(nums, target))  # Output: (2, 7)

Method 3: Sorting and Two-Pointer Technique

This approach involves sorting the array first, then using two pointers to find the pair. The time complexity is $O(n \log n)$ due to sorting, and space complexity is $O(1)$ if sorting is done in-place.

def find_two_sum(nums, target):

    nums_sorted = sorted(nums)

    left, right = 0, len(nums_sorted) - 1

    

    while left < right:

        current_sum = nums_sorted[left] + nums_sorted[right]

        if current_sum == target:

            return (nums_sorted[left], nums_sorted[right])

        elif current_sum < target:

            left += 1

        else:

            right -= 1

    return None

# Example usage:

nums = [2, 7, 11, 15]

target = 9

print(find_two_sum(nums, target))  # Output: (2, 7)

Choosing the Best Method

• Hash Set or Dictionary: Optimal for most cases due to $O(n)$ time complexity and relatively simple implementation. Suitable when you need to find pairs in unsorted arrays.
• Sorting and Two-Pointer: Useful when you need to work with sorted data or when space is a concern. Sorting the array may be less efficient if you need to perform this operation frequently.

Choose the method that best fits your specific problem constraints and requirements.