Given a 1-indexed array of integers numbers 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 [index1, index2]
where 1 <= index1 < index2 <= numbers.length.
The solution must use only constant extra space.
Input: numbers = [2,7,11,15], target = 9
Output: [1,2]
Explanation: 2 + 7 = 9. Return [1, 2].
Input: numbers = [2,3,4], target = 6
Output: [1,3]
Input: numbers = [-1,0], target = -1
Output: [1,2]
Constraints:
- 2 <= numbers.length <= 3 * 104
- -1000 <= numbers[i] <= 1000
- Exactly one solution exists. No extra space allowed.
Contents
- Approach 1 — Brute Force O(n²)
- Approach 2 — Two Pointers O(n)
- Complexity Analysis
Brute Force O(n²)
public int[] twoSum(int[] numbers, int target) {
for (int i = 0; i < numbers.length - 1; i++) {
for (int j = i + 1; j < numbers.length; j++) {
if (numbers[i] + numbers[j] == target) {
return new int[]{i + 1, j + 1};
}
}
}
return new int[]{};
}
Two Pointers O(n)
Because the array is sorted, place one pointer at the left and one at the right.
If their sum is less than target, move left right (increase sum); if greater, move right left (decrease sum).
public int[] twoSum(int[] numbers, int target) {
int left = 0, right = numbers.length - 1;
while (left < right) {
int sum = numbers[left] + numbers[right];
if (sum == target) return new int[]{left + 1, right + 1};
else if (sum < target) left++;
else right--;
}
return new int[]{}; // guaranteed to find answer
}
| Approach | Time | Space |
|---|
| Brute Force | O(n²) | O(1) |
| Two Pointers | O(n) | O(1) |