Two Sums Problem

Two Sums Problem

The Problem

Given an array of integers and a target sum, find two numbers that add up to the target. Return their indices.

Example:

nums = [2, 7, 11, 15]
target = 9
Answer: [0, 1] because nums[0] + nums[1] = 2 + 7 = 9

Your Task

Implement this function:

def two_sum(nums, target):
    """
    Find two numbers that add up to target.
    Return their indices.
    """
    # TODO: Your code here
    pass

# Test it
nums = [2, 7, 11, 15]
target = 9
result = two_sum(nums, target)
print(result)  # Should print [0, 1]

1. What is the time complexity of your algorythm?
2. Can you find an algorythm that works with a single loop ? O(n) complexity, linear time