Two Sum [Solution]

Below is a Python implementation of the two_sum function to find the indices of two numbers in the array that add up to the target:

from typing import List

def two_sum(nums: List[int], target: int) -> List[int]:
    """
    Return the indices of the two numbers in the array that add up to the target.

    Parameters:
    - nums: List of integers.
    - target: Target sum.

    Returns:
    - List[int]: Indices of the two numbers.
    """
    num_indices = {}  # Dictionary to store the indices of numbers

    for i, num in enumerate(nums):
        complement = target - num

        # Check if the complement is already in the dictionary
        if complement in num_indices:
            # Return the indices of the two numbers
            return [num_indices[complement], i]

        # Store the current number and its index in the dictionary
        num_indices[num] = i

    # If no solution is found, return an empty list
    return []

# Example usage:
nums1 = [2, 7, 11, 15]
target1 = 9
result1 = two_sum(nums1, target1)
print(result1)  # Output: [0, 1]

nums2 = [3, 2, 4]
target2 = 6
result2 = two_sum(nums2, target2)
print(result2)  # Output: [1, 2]

nums3 = [3, 3]
target3 = 6
result3 = two_sum(nums3, target3)
print(result3)  # Output: [0, 1]

This solution uses a dictionary num_indices to store the indices of numbers as we iterate through the array. It efficiently finds the complement needed to reach the target sum.

Time Complexity:

The time complexity is O(n), where n is the length of the input array.

Space Complexity:

The space complexity is O(n) due to the storage of indices in the dictionary.