Given a list of integers and a target, find the two indices (0-based) whose values add up to the target. Exactly one answer exists and you may not use the same element twice.
Input
- Line 1: n (
2 ≤ n ≤ 10^5)
- Line 2: n integers
- Line 3: the target
Output
The two indices i j with i < j, separated by a space.
Hint
A hash map from value → index gives an O(n) solution.
Read from standard input and write to standard output. 4 test cases in total (2 hidden). Tests for this language run inside your browser.