Two Sum II - Input Array Is Sorted
Medium· opposite ends· sorted input
Problem
A sorted array and a target are given. Find the two numbers that add up to the target and return their 1-based indices. Exactly one solution exists, and only constant extra space is allowed.
Examples
Input: numbers = [1,3,4,5,9], target = 10
Output: [1,5]
1 + 9 = 10, at 1-based positions 1 and 5.
Input: numbers = [-3,0,5], target = 2
Output: [1,3]
Constraints
- • 2 <= numbers.length <= 3 * 10^4
- • numbers is sorted in non-decreasing order
- • Exactly one solution exists
Hints & approach
Hint 1
A hash map works, but it uses extra space. Use the sorted order instead.
Hint 2
Start with the smallest and largest values. If the sum is too small, what should move?
Approachtry the hints first
Place left at index 0 and right at the last index. If numbers[left] + numbers[right] equals the target, return [left + 1, right + 1]. If the sum is too small, move left right to increase it; if too large, move right left to decrease it. Each move discards a value that cannot be part of any solution, so the scan is linear.
Time O(n) · Space O(1)