Hash Tables
Loading
Loading
Hash Tables
The move that turns almost every backwards search into a single pass.
By the end of this chapter
A nested loop that searches earlier elements is asking a membership question. Rearrange the condition so the thing you are looking for is computable, then look it up. For a pair summing to target, the partner of v is exactly target - v.
def pair_indices(nums, target): seen = {} for index, value in enumerate(nums): complement = target - value if complement in seen: # check BEFORE inserting return [seen[complement], index] seen[value] = index return []| Question | Rearranged into |
|---|---|
| Two values summing to t | Has t - v been seen? |
| Two values differing by d | Has v - d been seen? |
| A range summing to t | Has running - t been seen? |
| A repeat within k positions | Was v seen at an index within k? |
Can you recognise the pattern?
A nested loop where the inner one searches earlier elements for something specific.
Sign in to keep a note here. It is free, and nobody else can see it.
Sign inWhat this chapter was for:
Before moving on: try 3 practice problems.