The example problem
Given a list of numbers and a target, find the positions of two numbers that add up to the target. Exactly one such pair exists.
Input: nums = [3, 8, 5, 9, 4], target = 17 Output: [1, 3] (8 + 9 = 17)
Picture it
Think of a coat-check counter. Each arriving guest carries a number. Before hanging their coat, the attendant asks: “is there already a coat here whose number is exactly what this guest needs to reach the target?” If yes, those two guests are the pair. If not, the coat goes on the rack. The rack is a dictionary that maps number → position, so the check takes one glance instead of searching every coat.
The key idea
For each number x, the partner you need is target − x. Store what you have seen in a dictionary and look the partner up in O(1).
Python
def two_sum(nums, target):
seen = {} # coat rack: number -> ticket
for i, x in enumerate(nums):
need = target - x
if need in seen:
return [seen[need], i]
seen[x] = i
return []Practise hashing
- LeetCode 36Valid SudokuThree checklists for a Sudoku board
- LeetCode 128Longest Consecutive SequenceBeads on a ruler
- LeetCode 169Majority Element (Boyer–Moore)An election where opposite votes cancel
- LeetCode 219Contains Duplicate IIA coat check that only remembers recent guests
- LeetCode 242Valid AnagramTwo bags of letter tiles
- LeetCode 290Word PatternMatching symbols to words, both ways
- LeetCode 349Intersection of Two ArraysWho is on both guest lists?
- LeetCode 350Intersection of Two Arrays IIMatching fruit from two baskets
- LeetCode 387First Unique Character in a StringThe first guest with a one-off ticket colour
- LeetCode 447Number of BoomerangsThrowers standing equally far apart
- LeetCode 4544Sum IIFour bags of numbered balls that cancel out
- LeetCode 771Jewels and StonesSorting jewels from a bag of stones
- LeetCode 1394Find Lucky Integer in an ArrayA raffle number that matches its count
NeetCode 150 problems that use it
Arrays & Hashing ·
- LeetCode 217 · EasyContains DuplicateA stamp collector spots a repeat
- LeetCode 242 · EasyValid AnagramTwo bags of letter tiles
- LeetCode 1 · EasyTwo SumThe coat check counter
- LeetCode 49 · MediumGroup AnagramsSorting words into jars by their letters
- LeetCode 347 · MediumTop K Frequent ElementsThe k most frequent visitors
- LeetCode 271 · MediumEncode and Decode StringsParcels on a conveyor, each with a length label
- LeetCode 238 · MediumProduct of Array Except SelfTwo runners multiplying from each end
- LeetCode 36 · MediumValid SudokuThree checklists for a Sudoku board
- LeetCode 128 · MediumLongest Consecutive SequenceBeads on a ruler