LeetCode: Two Sum

Find two numbers in an array that add up to a specific target.

Solution

Create a dictionary to store the numbers we have seen so far, mapping each number to its index. For each number in the array, calculate its complement (i.e., target - number). Check if the complement exists in the dictionary. If it does, return the indices of the current number and its complement. If not, add the current number and its index to the dictionary and continue.

Note: The ValueError at the end is to handle cases where no solution is found. The problem states that exactly one solution exists. This is just a safeguard.

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        # Create a map of numbers
        # { value: index }
        nums_map = {}

        for idx, value in enumerate(nums):
            complement = target - value

            # If the complement is already in our nums_map, we are done.
            if complement in nums_map:
                return [nums_map[complement], idx]

            nums_map[value] = idx

        raise ValueError("No match found!")