Two Sum easy

Problem Statement

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

Example 1:

Input: nums = [2,7,11,15], target = 9 Output: [0,1] Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

Example 2:

Input: nums = [3,2,4], target = 6 Output: [1,2]

Steps:

1. Create a dictionary: We'll use a dictionary to store numbers and their indices. This allows for quick lookups.

2. Iterate through the array: For each number in the input array nums:

   • Calculate the complement: This is the number needed to reach the target ( target - current_number).
   • Check if the complement exists in the dictionary:
     • If it does, we've found our pair! Return the index of the current number and the index of the complement from the dictionary.
     • If it doesn't, add the current number and its index to the dictionary.

3. Handle cases where no solution is found: (Although the problem statement guarantees a solution, it's good practice to include this). This step is unnecessary in this specific case, because the problem states there is exactly one solution.

Explanation:

The key to solving this problem efficiently is using a hash table (dictionary in Python). A brute-force approach (checking every pair) would have a time complexity of O(n²). Using a hash table reduces this to O(n).

The dictionary stores each number encountered and its index. When we iterate, we check if the complement (the number needed to reach the target) is already in the dictionary. If it is, we've found the solution; otherwise, we add the current number and its index to the dictionary for future checks.

Code:

def twoSum(nums, target):
    """
    Finds two numbers in a list that add up to a target value.

    Args:
        nums: A list of integers.
        target: The target sum.

    Returns:
        A list containing the indices of the two numbers that add up to the target.  Returns an empty list if no solution is found.
    """
    num_map = {}  # Dictionary to store numbers and their indices

    for i, num in enumerate(nums):
        complement = target - num
        if complement in num_map:
            return [num_map[complement], i]  # Found the pair!
        num_map[num] = i  # Add the current number and its index to the dictionary

    return [] #Should not reach this point due to problem constraints.

Complexity:

• Time Complexity: O(n), where n is the length of the input array. We iterate through the array once. Dictionary lookups are O(1) on average.
• Space Complexity: O(n), in the worst case, we store all numbers from the input array in the dictionary.