Two Sum - Leetcode Solution

The "Two Sum" problem on LeetCode asks us to find two numbers in an array that add up to a given target.

The input for this problem consists of an array of integers and a target integer. We need to find two distinct integers in the array whose sum equals the target.

There are multiple ways to solve this problem, but the most efficient way is to use a hash map. We can iterate through the array, and for each element, check if the difference between the target and the element exists in the hash map. If it does, we have found our solution, and we can return the indices of the two numbers. If it doesn't, we can add the element and its index to the hash map, and continue iterating through the array.

Here's the solution in Python:

def twoSum(nums, target):
    """
    :type nums: List[int]
    :type target: int
    :rtype: List[int]
    """
    hashmap = {}  # initialize an empty hash map to store elements and their indices
    for i in range(len(nums)):
        if target - nums[i] in hashmap:
            # if the difference between target and current element exists in the hash map, we have found our solution
            return [hashmap[target - nums[i]], i]
        else:
            # otherwise, add the current element and its index to the hash map
            hashmap[nums[i]] = i

This solution has a time complexity of O(n), where n is the length of the input array, since we iterate through the array once. It also has a space complexity of O(n), since we store elements and their indices in a hash map.

1