JavaMediumHashing20 min
Find a pair with a target sum
Print indices i j with i<j and a[i]+a[j]=target. Choose the smallest j, then smallest i; print NONE if absent. Follow the stated ordering and edge-case conventions exactly. Interviewers use this task to probe boundary handling and collection selection.
Input
n, n integers, then target.
Output
Print indices i j with i<j and a[i]+a[j]=target. Choose the smallest j, then smallest i; print NONE if absent.
Constraints
0 <= n <= 100000; values and target in [-1000000000,1000000000].
Example
Input
4 2 7 11 15 9
Output
0 1
Example 2 input
5 1 1 4 4 7 5
Output
0 2
This example exercises deterministic tie-breaking with duplicate values.
Public test cases (2)
Input
4 2 7 11 15 9
Expected output
0 1
Input
3 3 3 3 6
Expected output
0 1
Hints (2)
- Identify the state needed to avoid recomputing work for each element.
- Scan left to right and store only the earliest index for each value.
Target complexity: time O(n) expected · space O(n)