LeetCode. 1. Two Sum

Problem

Approach

Scan the array once from left to right. Before processing nums[i], the map contains each value seen at an earlier index and that value’s index. For the current value, look up its complement, target - nums[i]. If it is present, the stored index and i form the answer. Otherwise, store the current value and index for later elements.

The map contains only earlier indices, so a match can never reuse the current element. LeetCode guarantees exactly one solution, so the scan will find and return that pair.

The complement is computed as a long before looking it up. If it is outside the int range, it cannot equal any array value and is skipped; this avoids overflow in target - nums[i].

Expected time complexity is O(N), with O(N) additional space.

Java

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

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

        for (int i = 0; i < nums.length; i++) {
            long complement = (long) target - nums[i];
            if (complement >= Integer.MIN_VALUE && complement <= Integer.MAX_VALUE) {
                Integer earlierIndex = earlierIndices.get((int) complement);
                if (earlierIndex != null) {
                    return new int[] { earlierIndex, i };
                }
            }

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

        throw new IllegalStateException("LeetCode guarantees exactly one solution");
    }
}