What Is the Two Sum Problem?

The Two Sum problem gives us an array of numbers and one target number. We need to find two numbers inside the array whose sum is equal to the target.

Usually, we return the indexes of those two numbers.

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

2 + 7 = 9

Answer = [0, 1]

Here, number 2 is at index 0, and number 7 is at index 1. So we return [0, 1].

Beginner-Friendly Idea

For every number, we ask one simple question:

“What number do I need to reach the target?”

For example, if the target is 9 and the current number is 7, then we need:

need = target - currentNumber
need = 9 - 7
need = 2

So if we already saw the number 2 before, then we have found the answer.

Why Do We Use a Hash Map?

A hash map helps us remember numbers we have already seen. It stores each number with its index.

number -> index
2      -> 0
7      -> 1

This makes the solution fast because checking if a number exists in a hash map is usually very quick.

Step-by-Step Explanation

Let us use this input:

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

Step 1

Start with an empty hash map. This hash map will store numbers and their indexes.

seen = {}

Step 2

First number is 2. The target is 9. So we need 7.

need = 9 - 2
need = 7

But 7 is not in the hash map yet. So we store 2 with its index.

seen = {
  2: 0
}

Step 3

Next number is 7. The target is 9. So we need 2.

need = 9 - 7
need = 2

Now 2 is already in the hash map. It is at index 0. The current number 7 is at index 1.

return [seen[need], i]
return [seen[2], 1]
return [0, 1]

How Does seen[need], i Work?

This part is very important:

return [seen[need], i]

seen[need] gives the index of the number we already found before. i is the index of the current number.

So this means:

return [index_of_old_number, index_of_current_number]

In our example, seen[2] gives 0, and the current index is 1. So the answer is [0, 1].

Example 1

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

Output:
[0, 1]

Explanation:
nums[0] + nums[1] = 2 + 7 = 9

Example 2

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

Output:
[1, 2]

Explanation:
nums[1] + nums[2] = 2 + 4 = 6

Python Code

Here is the complete Python solution using a hash map.

def two_sum(nums, target):
    seen = {}

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

        if need in seen:
            return [seen[need], i]

        seen[num] = i

    return []


# Example 1
nums = [2, 7, 11, 15]
target = 9
print(two_sum(nums, target))  # Output: [0, 1]

# Example 2
nums = [3, 2, 4]
target = 6
print(two_sum(nums, target))  # Output: [1, 2]

Java Code

Here is the complete Java solution using a HashMap.

import java.util.HashMap;
import java.util.Map;
import java.util.Arrays;

public class TwoSum {
    public static int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> seen = new HashMap<>();

        for (int i = 0; i < nums.length; i++) {
            int num = nums[i];
            int need = target - num;

            if (seen.containsKey(need)) {
                return new int[] { seen.get(need), i };
            }

            seen.put(num, i);
        }

        return new int[] {};
    }

    public static void main(String[] args) {
        int[] nums1 = {2, 7, 11, 15};
        int target1 = 9;
        System.out.println(Arrays.toString(twoSum(nums1, target1)));
        // Output: [0, 1]

        int[] nums2 = {3, 2, 4};
        int target2 = 6;
        System.out.println(Arrays.toString(twoSum(nums2, target2)));
        // Output: [1, 2]
    }
}

Time and Space Complexity

Time Complexity: O(n)

We visit each number only one time. That is why the time complexity is O(n).

Space Complexity: O(n)

We use a hash map to store numbers and their indexes. In the worst case, we may store many numbers, so the space complexity is O(n).

Final Summary

The Two Sum problem is about finding two numbers that add up to a target. The easiest fast solution is to use a hash map. For each number, we calculate the number we need. If that needed number already exists in the hash map, we return both indexes.