Two Sum Problem
The problem
You get a list of numbers nums and a number target. Find the two positions whose numbers add up to target. Each input has exactly one answer, and you can't use the same position twice.
Example: nums = [2, 7, 11, 15], target = 9 → answer [0, 1], because 2 + 7 = 9.
1. Try it yourself
Click two numbers that add up to .
2. Need a hint?
Hint 1
Checking every pair works, but it takes about n × n steps. Can you do it in one pass?
Hint 2
For each number x, the number you need is target − x. We call it the complement.
Hint 3
Keep a table (hash map) of numbers you've already seen and their positions. Before you store x, check whether its complement is already in the table.
3. Watch the hash-map solution
Current number–
Needed (target − x)–
Seen table { number → position }
4. Brute force vs hash map
Number of checks for the numbers above:
Brute force (every pair)–O(n²)
Hash map (one pass)–O(n)
Show the code (Python)
def two_sum(nums, target):
seen = {} # number -> position
for i, x in enumerate(nums):
need = target - x
if need in seen:
return [seen[need], i]
seen[x] = i
return []
One Response