Two Sum

ArrayHash Table

10 min

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

Example 1:

Input: nums = [2, 7, 11, 15], target = 9

Given nums = [2, 7, 11, 15], target = 9

The numbers at indices 0 and 1 add up to 9.

Output: [0, 1]

Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

Solution (One-pass Hash Table)

A common and efficient way to solve the Two Sum problem is by using a hash map (or a dictionary in Python). This approach allows us to find the solution in a single pass through the array.

Algorithm Steps

Create a hash map to store numbers we've seen and their indices.
Iterate through the input array nums.
For each number, calculate its complement by subtracting it from the target.
Check if the complement exists in the hash map.
If it exists, we have found our pair. Return the index of the complement (from the map) and the index of the current number.
If the complement does not exist in the map, add the current number and its index to the map.
Continue until the solution is found.

Nums (comma-separated):

Target:

Map: {}

Complement: -

Start with nums = [2, 7, 11, 15] and target = 9.

Two Sum Solution


class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        num_map = {}
        for i, num in enumerate(nums):
            complement = target - num
            if complement in num_map:
                return [num_map[complement], i]
            num_map[num] = i