ProblemEasyLeetCode #14 min read

Two Sum

Find two indices whose values sum to a target. The classic O(n) hashmap warm-up.

arrayshashmap

Intro

Given an array of integers and a target, return the indices of two numbers that add to the target. The brute-force O(n²) is two nested loops; the right approach is a single pass with a hashmap that turns the lookup into O(1).

Key insight

For each element x, the partner you need is `target - x`. Keep a hashmap of value → index as you walk.

Approach

1Iterate over the array.
2For each element x, compute need = target - x.
3If need is in the map, return [map[need], current index].
4Otherwise put x → current index in the map.

Complexity

Time

O(n)

Space

O(n)

Code

Snippetjava

int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> seen = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        int need = target - nums[i];
        if (seen.containsKey(need)) return new int[]{seen.get(need), i};
        seen.put(nums[i], i);
    }
    return new int[]{-1, -1};
}

Snippetpython

def twoSum(nums, target):
    seen = {}
    for i, x in enumerate(nums):
        if target - x in seen:
            return [seen[target - x], i]
        seen[x] = i

Pitfalls

Putting the value into the map before the lookup — risks pairing an element with itself.
Returning the values instead of the indices.

Variants & follow-ups

3Sum (LC 15)
4Sum (LC 18)
Two Sum II — sorted (LC 167)