Find the two that add up
A reconciliation tool looks for the two entries that together explain a difference.
- Return the two positions, counting from zero, smaller position first.
- If several pairs would work, return the one whose second position comes first.
- No pair means an empty list.
- A value may not be paired with itself, but two equal values at different positions are fine.
pair_summing_to(values: list<int>, target: int) → list<int>
Where you start
def pair_summing_to(values: list[int], target: int) -> list[int]:
Worked examples
| Call | Result |
|---|---|
pair_summing_to([2, 7, 11, 15], 9) | [0, 1] |
pair_summing_to([3, 2, 4], 6) | [1, 2] |
pair_summing_to([3, 3], 6) | [0, 1] |
pair_summing_to([1, 2], 99) | [] |
Hint
Walk once, and for each value ask whether the number that would complete it has already gone by.
Reference solution in Python
def pair_summing_to(values: list[int], target: int) -> list[int]:
seen = {}
for j, v in enumerate(values):
need = target - v
if need in seen:
return [seen[need], j]
if v not in seen:
seen[v] = j
return []