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)
1#include <stdlib.h>
2
3int* twoSum(int* numbers, int numbersSize, int target, int* returnSize) {
4 *returnSize = 2;
5 int* result = (int*)malloc(sizeof(int) * 2);
6 int left = 0, right = numbersSize - 1;
7 while (left < right) {
8 int sum = numbers[left] + numbers[right];
9 if (sum == target) {
10 result[0] = left + 1;
11 result[1] = right + 1;
12 return result;
13 } else if (sum < target) {
14 left++;
15 } else {
16 right--;
17 }
18 }
19 return NULL; // This point should never be reached due to problem constraints.
20}The C solution uses a while loop to implement the two-pointer technique. The left and right pointers are adjusted based on the sum compared to the target, ensuring the correct indices are returned in ascending order due to the sorted nature of the input array.
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 Java approach implements a binary search within a loop over the numbers. For each number, the binary search identifies if the complement required to reach the target exists within the rest of the list.