Advanced · Techniques · 207 of 264
Two numbers to a target
Find the first pair of positions i < j whose numbers add up to the target: the smallest j, and for that j the smallest i. Use a dictionary of numbers seen so far.
Input: whole numbers on one line, then the target. Output: i j (from 0), or none
Examples
Input
2 7 11 15 9
Output
0 1
Input
3 2 4 6
Output
1 2
Input
1 2 3 7
Output
none
One more test checks other inputs when you press Check.
Stuck? The idea behind techniques
Some problems have a known shape. Two pointers move from both ends of a sorted list. A sliding window keeps a running total as it moves, adding one item and taking one away.
A dictionary of what has been seen turns a search inside a loop into a single lookup.
nums = [2, 7, 11, 15]
target = 9
seen = {}
for i, x in enumerate(nums):
if target - x in seen:
print(seen[target - x], i)
seen[x] = iWatch for: A loop inside a loop over the same long list is slow: the hidden tests may use big inputs.