Blind 75 · Arrays & Hashing
Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
You can return the answer in any order.
Example 1: Input: nums = [2,7,11,15], target = 9 Output: [0,1] Explanation: nums[0] + nums[1] == 9, so return [0,1]. Example 2: Input: nums = [3,2,4], target = 6 Output: [1,2] Example 3: Input: nums = [3,3], target = 6 Output: [0,1]
2 <= nums.length <= 10^4 -10^9 <= nums[i] <= 10^9 -10^9 <= target <= 10^9 Exactly one valid answer exists.
Hash sets and hash maps — expected O(1) membership and lookup, and what "expected" costs when hashes collide.
Array traversal, and the habit of asking what a second pass buys over a nested loop.
Try every pair and check whether it sums to the target. Correct, and the baseline the real answer improves on.
1. For each index i, walk every index j after it.
2. If nums[i] + nums[j] equals target, return those two indices.
3. The problem guarantees a solution, so the loops always find one.
Time O(n^2). Space O(1).
At each number the question is not "which pair works" but "have I already seen the number that completes this one" — and target minus the current value names it exactly. A map from value to index answers that in constant time, so one pass is enough. Storing AFTER checking is what stops an element pairing with itself.
1. Keep a map from value to the index it was seen at.
2. For each value x at index i, compute the complement target - x.
3. If the complement is in the map, return its index and i.
4. Otherwise store x -> i and carry on.
Time O(n) — one pass with expected O(1) lookups. Space O(n) for the map.