Two Sum
Two Sum is an easy Arrays & Hashing problem from the Blind 75. The key pattern is hash map of complements, and a good solution runs in O(n) time.
Problem
Given an integer array and a target, return the two distinct zero-based indices whose values add to the target.
Examples
Example 1
Input
{"nums":[4,10,-3,7],"target":7}Output
[1,2]Example 2
Input
{"nums":[3,3],"target":6}Output
[0,1]Example 3
Input
{"nums":[-5,8,2,11],"target":6}Output
[0,3]Approach
For each value x, look up target − x among the values seen so far, then store x with its index. One pass finds the pair.
| Pattern | Hash map of complements |
|---|---|
| Time | O(n) |
| Space | O(n) |
Watch out for
Check for the complement before inserting x, so a value is never paired with itself while equal duplicates like [3,3] still work.