Two Sum II - Input Array Is Sorted
The array is sorted, so two pointers act like a binary search on the pair sum — nudge l up or r down until they hit the target.
The problem
Given a 1-indexed array `numbers` sorted in non-decreasing order and a `target`, find the two numbers that add up to it and return their indices as `[index1, index2]`, each added by one.
There's exactly one solution, the same element can't be used twice, and the solution must use only constant extra space.
The approach
My idea is to fuse the typical two-pointer approach with binary search: `l` at the start, `r` at the end. If `numbers[l] + numbers[r]` equals the target, that's the answer.
If the sum is greater than the target I decrement `r` to a smaller value; if it's less I increment `l` to a larger one. I return `[l+1, r+1]` because the array is 1-indexed, and I don't need a default return since the problem guarantees exactly one solution.
The solution
/**
* @param {number[]} numbers
* @param {number} target
* @return {number[]}
*/
var twoSum = function(numbers, target) {
let [l,r] = [0,numbers.length-1]
while(l<r) {
if(numbers[l] + numbers[r] == target) {
return [l+1,r+1]
}
else if(numbers[l] + numbers[r] > target) {
r--
}
else {
l++
}
}
};Time O(n)Space O(1)