Problem statement
Given an unsorted array and a target, return the indices of two numbers that add up to the target.
The lawful route
Scan once while recording each inspected value by its index. For each candidate, look up the complement required to reach the target.
Invariant
Every value before the current candidate is recorded with its index, so any valid earlier complement can be recovered in constant time.
Proof vocabulary used
- Problem Space
- Answer Space
- Recorder
- Complement Lookup
- Invariant
Complexity
Time O(n) · Space O(n)