Two Sum

Given an array of integers and a target, return the indices of the two numbers that add up to the target. Exactly one valid pair is guaranteed to exist.

EasyMust DoHashingLeetCode

Why solve this?

It's the canonical first lesson in trading O(n^2) brute force for O(n) by remembering what you've already seen.

Pattern recognition

"Find a pair that sums to X" in a single array is almost always a hash-map complement-lookup problem, not a nested loop.

Prerequisites

Arrays
Hashing

Hints

A brute-force nested loop works but is O(n^2) — can you avoid the second loop?
For each number, what value would you need to have already seen to complete a pair?
Store each number's index in a hash map as you scan once, left to right.

Approach

Walk the array once. For each element `x` at index `i`, compute `complement = target - x`. If `complement` is already in the hash map, you've found your pair — return its stored index and `i`. Otherwise, store `x -> i` in the map and continue. Because every insert and lookup is O(1) on average, the whole scan is O(n).

Java solution

Solution.java

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);
        }
        throw new IllegalArgumentException("No two sum solution");
    }
}

Time: O(n)Space: O(n)