Trade memory for speed: store what you have seen in a Map or Set so each lookup is O(1) instead of scanning again.
Used for
need 9 - 2 = 7: not seen
need 9 - 7 = 2: seen at 0
Target 9. You are on 4, with 3 and 5 remembered. Is there a match?
Not quite. The partner needed is 9 - 4 = 5, and 5 was already seen. So 5 + 4 = 9.
Step 1 of 5
Goal: find two numbers in [2, 7, 11, 15] that add up to 9. Checking every pair is slow. Trick: for a number x, the partner we need is 9 - x. If we remember every number seen so far, "have I seen the partner?" is answered instantly.
Step 2 of 5
First number: 2. Its partner would be 7. Nothing is remembered yet, so write down 2 (at position 0).
Step 3 of 5
Next number: 7. Its partner would be 2, and 2 is written down at position 0. Found: positions 0 and 1.
Step 4 of 5
Each lookup in the remembered list (a hash map) takes one step, so the whole search is a single pass instead of checking every pair. Trading a little memory for speed is the hash map pattern.
Step 5 of 5
Your turn.
Hash Map & Set (JS Map and Set)Polynomial Rolling HashHash TableLeast Recently Used (LRU) CacheBloom Filter
function twoSum(nums, target) { const idx = new Map(); for (let i = 0; i < nums.length; i++) { if (idx.has(target - nums[i])) return [idx.get(target - nums[i]), i]; idx.set(nums[i], i); }}