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 return new int[0]; // Guarantee issue due to constraints
15 }
16}
The C# implementation uses a similar approach as previous languages, relying on a fixed-size array for the result and the typical two-pointer adjustment strategy to find the solution.
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.