Why it works
- Each number knows its partner in advance: the target minus the number. The only question is whether we have met it already, and the map answers that at once.
- Look up first, store after. Otherwise the first 5 would find itself in the map and return [0, 0].
- If the pair is at j < i, then by the time we reach i the number at j is in the map. So the pair is never missed, and one pass is enough.
Complexity
Time O(n): one pass, and a lookup or a store in the map takes O(1) on average. Memory O(n): the map may hold every number.
nextNow solve it yourself, no hints.
Solve on LeetCode ↗