283. Two That Add Up
Core1000 ms256 MBSolved by 0%
Given n integers and a target t, print the two positions i j with
i < j such that a[i] + a[j] == t. If no such pair exists, print None.
If several pairs work, print the one whose SECOND index is smallest. That makes the answer unique, and it is exactly what the natural one-pass solution finds anyway.
Checking every pair is quadratic. Instead, as you walk the array, ask whether the partner you need has already been seen. A map from value to index answers that in one lookup.
Constraints - `1 ≤ n ≤ 200000` - `-1000000000 ≤ a[i] ≤ 1000000000` - `-2000000000 ≤ t ≤ 2000000000`
Input
The first line contains two integers n and t.
The second line contains n integers.
Output
Print two 0-based indices separated by a space, or None if no pair sums to t.
Input4 9
2 7 11 15
Output0 1
Notehas its answer at the front
Input1 1
1
OutputNone
Noteis a single element, and a pair needs two
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.
Hint 1Where to start
Hint 2The approachOpen hint 1 first. This one carries on from it.
Hint 3PseudocodeOpen hint 2 first. This one carries on from it.
Hint 4Full solutionOpen hint 3 first. This one carries on from it.