Two Sum in Java: two useful approaches

Given a list of integers and a target, return the indices of two values whose sum equals the target.

Start with the obvious solution

Checking every pair is easy to verify but takes O(n²) time:

int[] twoSumSlow(int[] nums, int target) {
    for (int left = 0; left < nums.length; left++) {
        for (int right = left + 1; right < nums.length; right++) {
            if (nums[left] + nums[right] == target) {
                return new int[] {left, right};
            }
        }
    }

    return new int[0];
}

Trade memory for speed

As we scan, a HashMap records each value's index. For the current value, we ask whether its complement has already appeared.

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

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

    for (int index = 0; index < nums.length; index++) {
        int complement = target - nums[index];
        if (seen.containsKey(complement)) {
            return new int[] {seen.get(complement), index};
        }
        seen.put(nums[index], index);
    }

    return new int[0];
}

The expected time is O(n) and the extra space is O(n).

A small Java detail

The map stores boxed Integer values because Java collections cannot hold primitive int values directly. Autoboxing handles those conversions for us, keeping the implementation concise.