LeetCode 1 · Easy · Arrays & Hashing

Two Sum

Given an integer array nums and an integer target, return the indices of the two numbers that add up to target. You may not use the same element twice.

O(n)time
O(n)space
1 passhash map

nums: 2–16 integers, −999 to 999 · target: −1998 to 1998

need = target − n

seen hash map · value → index · bucket = value mod 8

public int[] twoSum(int[] nums, int target) { Map<Integer, Integer> seen = new HashMap<>(); // value -> index for (int i = 0; i < nums.length; i++) { int n = nums[i]; int need = target - n; if (seen.containsKey(need)) { return new int[] { seen.get(need), i }; } seen.put(n, i); } return new int[0];}
i
—
n
—
need
—
need mod 8
—
seen
{}

Why it works

  1. Brute force tries every pair: two nested loops, O(n²).
  2. Flip the question. For each n you already know the partner you need: target − n. The map answers "have I seen it?" in O(1) on average.
  3. Look up before you store. Otherwise n could pair with itself: in [3,2,4] with target 6, the 3 must not match its own 3.
  4. Store value → index, because the answer asks for indices, not values. A repeated value overwrites its index; either index is a valid answer.
  5. One pass: a pair is found the moment its second number arrives. O(n) time, O(n) space.
  6. Sorted input? Then two pointers from both ends need no map, O(1) space. That is Two Sum II, the same idea you meet again in Valid Palindrome.