Sponsored
Sponsored
This approach utilizes a two-pointer technique taking advantage of the sorted nature of the input array. The first pointer starts at the beginning of the array while the second starts at the end. By evaluating the sum at these two pointers, you can determine how to move the pointers:
This method operates in O(n) time and uses O(1) additional space.
Time Complexity: O(n)
Space Complexity: O(1)
1public class Solution {
2 public int[] twoSum(int[] numbers, int target) {
3 int left = 0, right = numbers.length - 1;
4 while (left < right) {
5 int sum = numbers[left] + numbers[right];
6 if (sum == target) {
7 return new int[] { left + 1, right + 1 };
8 } else if (sum < target) {
9 left++;
10 } else {
11 right--;
12 }
13 }
14 throw new IllegalArgumentException("No solution exists"); // Safe due to problem constraints.
15 }
16}The Java solution also applies the two-pointer strategy, employing a while loop to find the right indices that add up to the target. A custom exception is thrown if no solution is found, which is safeguarded by constraints.
This approach also takes advantage of the sorted array, integrating binary search for a more theoretically robust approach. For every element in the array, a binary search is employed to find the complement such that the sum is equal to the target:
i.target - numbers[i].Time Complexity: O(n log n) (due to binary search)
Space Complexity: O(1)
The C solution incorporates a binary search helper function to look for the complement of each element from the remaining array indices. Once found, it returns the indices incremented by one, adhering to the input constraints.