The Two Sum problem is a classic algorithmic challenge where the goal is to find two numbers in an array that add up to a specific target sum. This implementation uses a hash map (dictionary in Python) to achieve an efficient solution.

Program Structure

1. Function Definition: We define a function two_sum that takes a list of integers nums and an integer target.
2. Hash Map Initialization: We create an empty dictionary to store the numbers and their corresponding indices.
3. Iteration: We loop through the list of numbers, and for each number, we check if the complement (i.e., target - number) exists in the dictionary.
4. Result: If the complement exists, we return the indices of the two numbers. If not, we add the current number and its index to the dictionary.

Python Code

def two_sum(nums, target):
    """
    Find two numbers in `nums` that add up to `target`.

    Parameters:
    nums (list): A list of integers.
    target (int): The target sum.

    Returns:
    list: Indices of the two numbers that add up to the target, or an empty list if no solution exists.
    """
    # Create a hash map to store number and its index
    num_map = {}

    # Iterate over the list of numbers
    for index, number in enumerate(nums):
        # Calculate the complement
        complement = target - number

        # Check if complement exists in the hash map
        if complement in num_map:
            return [num_map[complement], index]

        # Add the number and its index to the hash map
        num_map[number] = index

    # Return an empty list if no solution is found
    return []

# Example usage
nums = [2, 7, 11, 15]
target = 9
result = two_sum(nums, target)
print(f"Indices of the numbers that add up to {target}: {result}")

Explanation

The function two_sum works as follows:

• It initializes an empty dictionary num_map to keep track of numbers and their indices.
• As it iterates through the list nums, it calculates the complement for each number.
• If the complement is found in num_map, it means we have identified the two numbers that sum up to the target. The function then returns their indices.
• If the complement is not found, it adds the current number and its index to num_map for future reference.

Complexity Analysis

The time complexity of this solution is O(n), where n is the number of elements in the input list nums. The space complexity is also O(n) due to the storage of elements in the hash map.

Explanation of the Code:

• Function Definition: The two_sum function accepts a list of integers (nums) and a target integer (target).
• Hash Map: A dictionary (num_map) is used to store each number and its index as we iterate through the list.
• Iteration: The program checks for the complement of each number (i.e., target - number) and looks it up in the hash map.
• Return Indices: If the complement is found, the indices of both numbers are returned; otherwise, the current number and its index are added to the hash map.
• Output Example: An example is provided to demonstrate how to use the function and print the result.