ArrayTwo Pointers
The array is sorted in non-decreasing order. Find two different positions whose values add up to the target. Exactly one solution exists. Use only O(1) extra space.
Input
Line 1: n. Line 2: n sorted integers. Line 3: the target.
Output
Print the two positions as 1-based indices, smaller first, separated by a space.
Constraints
2 <= n <= 5 * 10^4 -10^9 <= each value, target <= 10^9
Example 1
Input
4 2 7 11 15 9
Output
1 2
2 + 7 = 9, at positions 1 and 2.
Example 2
Input
3 -1 0 3 2
Output
1 3
-1 + 3 = 2, at positions 1 and 3.