#1
Two Sum
Easy HashMap complement lookup
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Return the indexes of the two numbers that add up to target. Exactly one answer exists and the same element can't be used twice.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: two indexes whose values add up to target.
Why this works: for each number x, the partner you need is target - x. A map from value to index answers "have I seen it?" in O(1).
Example: [2, 7, 11, 15], target 9
2: need 7, not seen; store 2→07: need 2, seen at 0 → [0, 1]
✦Hints open one at a time
For each number x, you need target − x.
Store numbers you've already seen in a HashMap: value → index.
↗Approach
One pass: before inserting x, look up target − x. If it's there, you've found the pair. Checking before inserting stops an element pairing with itself.
</>Solution (Java)
import java.util.*;
class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> seen = new HashMap<>(); // value -> index
for (int i = 0; i < nums.length; i++) {
Integer j = seen.get(target - nums[i]);
if (j != null) return new int[]{j, i};
seen.put(nums[i], i);
}
return new int[0];
}
}!Common mistake
Inserting x first and then looking up target − x, which can return the same index twice when x = target / 2.
Complexity
- Time: O(n).
- Space: O(n).
Topic: Hashing
🎬 Episodes 37–39: video coming soon