Two Sum

Two Sum is the classic hash map complement problem. For each number, ask: "Have I already seen the number that pairs with this one to reach the target?"

Problem

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

Assumption for the usual LeetCode version:

• exactly one answer exists
• the same element cannot be used twice

First Attempt

This solution stores numbers we have already seen:

public int[] twoSum(int[] nums, int target) {
    var m = new HashMap<Integer, Integer>();
    m.put(nums[0], 0);

    for (int i = 1; i < nums.length; i++) {
        if (m.containsKey(target - nums[i])) {
            return new int[] { m.get(target - nums[i]), i };
        } else {
            m.put(nums[i], i);
        }
    }

    return new int[] { -1, -1 };
}

The core idea is correct. If the current value is nums[i], then the value we need is:

target - nums[i]

If that complement is already in the map, we have the answer.

What To Tune

The first version preloads nums[0] into the map and starts the loop from index 1. That works when nums has at least one element.

A slightly cleaner version starts from index 0 and does the same logic for every element:

1. compute the complement
2. check whether the complement was seen earlier
3. store the current number and index

That also avoids special-casing the first element.

Final Version

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

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

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

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

            seen.put(nums[i], i);
        }

        return new int[] { -1, -1 };
    }
}

Walkthrough

Input:

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

Steps:

The map stores the past, not the future. That is why the same element cannot accidentally pair with itself.

Duplicate Values

This handles duplicates correctly.

Example:

nums = [3, 3]
target = 6

At index 0, store 3 -> 0.

At index 1, complement is 3, and the map already has index 0.

Return:

[0, 1]

Complexity

Takeaways

• Store values you have already seen with their indices.
• For each value, look for target - nums[i].
• Check before inserting the current value, so an element is not reused with itself.
• This pattern is useful whenever a problem asks whether a prior value can complete the current value.