133. Sorted Pair Finder
A museum sells entry packages priced in whole rupees, and its price list nums is kept in strictly increasing order. A visitor wants to buy exactly two different packages whose prices add up to target.
Return the positions of those two packages as an array [i, j] using 1-based indexing, with i < j. Several pairs may work; in that case return the one with the smallest i. If no two packages add up to target, return [-1, -1]. Aim for a solution that reads each price only a few times and uses constant extra space.
Example 1
- Input:
- nums = [2,5,8,13,21], target = 26
- Output:
- [2,5]
- Explanation:
Prices 5 and 21 add up to 26. They sit at 1-based positions 2 and 5, so the answer is [2,5].
Example 2
- Input:
- nums = [-6,-1,0,4,9], target = 3
- Output:
- [1,5]
- Explanation:
Two pairs add up to 3: -6 and 9 (positions 1 and 5) and -1 and 4 (positions 2 and 4). The pair with the smaller i is [1,5].
Example 3
- Input:
- nums = [1,2,4], target = 10
- Output:
- [-1,-1]
- Explanation:
The largest possible sum is 2+4=6, which is below 10, so no pair exists.
Constraints
1 ≤ nums.length ≤ 105
-109 ≤ nums[i] ≤ 109, strictly increasing
-109 ≤ target ≤ 109
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Expected complexity
- Time
- O(n)
- Space
- O(1)