Two Sum II — Input Array Is Sorted
Problem
Given a 1-indexed array of integers numbers that is already sorted in non-decreasing order, find two numbers such that they add up to a specific target. Return the indices of the two numbers, 1-indexed, as an array of length 2.
Examples
Example 1
Input: numbers = [2,7,11,15], target = 9
Output: [1,2]
Explanation: numbers[0] + numbers[1] = 2 + 7 = 9, returned 1-indexed.
Example 2
Input: numbers = [2,3,4], target = 6
Output: [1,3]
Explanation: numbers[0] + numbers[2] = 2 + 4 = 6.
Constraints
- •
2 <= numbers.length <= 3 * 10^4 - •
-1000 <= numbers[i] <= 1000 - •
numbers is sorted in non-decreasing order - •
Exactly one valid answer exists
Hints
Hint 1
The array being sorted is the whole point — it means you don't need a hash map like unsorted Two Sum.
Hint 2
Start pointers at both ends. What does it tell you if the current sum is too big? Too small?
Hint 3
Because it's sorted, moving the left pointer only ever increases the sum, and moving the right pointer only ever decreases it — that monotonicity is what makes two pointers correct here.
Solutions
public int[] twoSumHashMap(int[] numbers, int target) {
Map<Integer, Integer> seen = new HashMap<>();
for (int i = 0; i < numbers.length; i++) {
int complement = target - numbers[i];
if (seen.containsKey(complement)) {
return new int[]{seen.get(complement) + 1, i + 1};
}
seen.put(numbers[i], i);
}
throw new IllegalArgumentException("No solution");
}Time: O(n) · Space: O(n)