Two Sum II - Sorted Array

Given a 1-indexed array of integers numbers that is sorted in non-decreasing order and an integer target, find two numbers that add up to target. Return the indices of the two numbers as [index1, index2] where 1 <= index1 < index2. Exactly one solution exists; you may not use the same element twice.

• 1-indexed means the first element has index 1 (so return [left+1, right+1] when using 0-based indices).
• The array is sorted, so we can use two pointers without extra space.

• Because the array is sorted, a two-pointer approach works: put one pointer at the start (smallest) and one at the end (largest). If the sum is too small, the only way to increase it is to move the left pointer right (to a larger value). If the sum is too large, move the right pointer left (to a smaller value). So we never miss the pair.
• When left < right: if numbers[left] + numbers[right] == target, we are done; if the sum is less than target, left++; else right--. Each step eliminates a candidate and we are guaranteed to find the unique pair.

High-level: Use two pointers left = 0 and right = n - 1. If the sum equals target, return [left+1, right+1]. If the sum is less than target, increment left; if greater, decrement right. Repeat until the pair is found.

Steps:

1. left = 0, right = numbers.length - 1.
2. While left < right: sum = numbers[left] + numbers[right]. If sum == target, return [left+1, right+1]. If sum < target, left++; else right--.
3. (Guaranteed to find.)

• Time: O(n).
• Space: O(1).

• Three sum: find all triplets that sum to 0.