Look up the partner
Find two values that add up to a target in one pass. About 9 minutes.
You know exactly who you're looking for
You have ₹9 of change to spend at a canteen and want two items that cost exactly that. When you pick up a ₹3 samosa, you don't need to search: the only partner that works costs exactly ₹6.
So walk the prices once. At each one, the partner you need is the target minus this price. Ask one question: have I already seen that partner?
Need 6. Not seen yet. Store 3 → 0.
Remember where you saw each value
The answer is a pair of positions, so the map stores each value with the box you saw it in. At each box, look up the partner first. If it's there, you have your two positions. If not, store this value and its box, so a later value can find it.
Look up before you store. Otherwise a 3 with a target of 6 could pair with itself.
where = {}
for j, x in enumerate(nums):
need = target - x
if need in where:
return [where[need], j]
where[x] = jThe numbers are 4, 5, 2 and the target is 7. At the 2, what do you look up?
- A5
- B2
- C7
Show the answer
5. 7 − 2 = 5, and 5 was stored at box 1, so the answer is boxes 1 and 2.
Two values, one target
nums is not sorted. Exactly one pair of different positions i < j has nums[i] + nums[j] == target. Return [i, j].
nums = [3, 8, 1, 7, 5], target = 9 → [1, 2]
2 ≤ n ≤ 500,000 · −100,000,000 ≤ each value, target ≤ 100,000,000