Problem Statement:
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 number. Let these two numbers be numbers[index1] and numbers[index2] where 1 <= index1 < index2 <= numbers.length.
Return the indices of the two numbers, index1 and index2, added by one as an integer array [index1, index2] of length 2.
The tests are generated such that there is exactly one solution. You may not use the same element twice.
Your solution must use only constant extra space.
Examples:
Example 1:
Input: numbers = [2,7,11,15], target = 9
Output: [1,2]
Explanation: The sum of 2 and 7 is 9. Therefore, index1 = 1, index2 = 2. We return [1, 2].
Example 2:
Input: numbers = [2,3,4], target = 6
Output: [1,3]
Explanation: The sum of 2 and 4 is 6. Therefore index1 = 1, index2 = 3. We return [1, 3].
Example 3:
Input: numbers = [-1,0], target = -1
Output: [1,2]
Explanation: The sum of -1 and 0 is -1. Therefore index1 = 1, index2 = 2. We return [1, 2].
Constraints:
2 <= numbers.length <= 3 * 104-1000 <= numbers[i] <= 1000numbersis sorted in non-decreasing order.The tests are generated such that there is exactly one solution.
Approach:
- Initialize two pointers:.
i = 0(start of array)j = numbers.length - 1 (end of array)
- Loop until
i < j- Calculate
sum = numbers[i] + numbers[j]. - If
sum > target, movejleft (decreasej) - If
sum < target, moveiright (increasei) - If
sum === target, return[i + 1, j + 1](1-based index)
- Calculate
Visualisation:
Time Complexity:
Time Complexity = O(n)
Space Complexity:
Space Complexity = O(1)
Dry Run
Input:
numbers = [4, 1, 2] target = 3
State Transitions:
Note: This is a two-pointer approach assuming the input array is sorted in non-decreasing order. Step 1: Initialize → i = 0, j = 2 (pointing to numbers[0] = 4, numbers[2] = 2) Step 2: → sum = numbers[i] + numbers[j] = 4 + 2 = 6 → sum > target → decrement j → j = 1 Step 3: → sum = numbers[i] + numbers[j] = 4 + 1 = 5 → sum > target → decrement j → j = 0 Now i = 0, j = 0 → i is not less than j → loop ends
Final Output: undefined
Final State: Loop exited without finding a valid pair since the array is not sorted in non-decreasing order as required by the two-pointer approach.
var twoSum = function(numbers, target) {
let i = 0;
let j = numbers.length - 1;
while( i < j){
let sum = numbers[i] + numbers[j];
if(sum > target) {
--j;
} else if(sum < target) {
++i;
} else {
return [i+1, j+1]
}
}
};
from typing import List
def twoSum(numbers: List[int], target: int) -> List[int]:
i = 0
j = len(numbers) - 1
while i < j:
sum = numbers[i] + numbers[j]
if sum > target:
j -= 1
elif sum < target:
i += 1
else:
return [i + 1, j + 1]
return []
class Solution {
public int[] twoSum(int[] numbers, int target) {
int i = 0;
int j = numbers.length - 1;
while(i < j) {
int sum = numbers[i] + numbers[j];
if(sum > target) {
--j;
} else if(sum < target) {
++i;
} else {
return new int[] { i + 1, j + 1 };
}
}
return new int[] {};
}
}
#include <vector>
using namespace std;
vector twoSum(vector& numbers, int target) {
int i = 0;
int j = numbers.size() - 1;
while(i < j) {
int sum = numbers[i] + numbers[j];
if(sum > target) {
--j;
} else if(sum < target) {
++i;
} else {
return {i + 1, j + 1};
}
}
return {};
}
#include <stdio.h>
#include <stdlib.h>
int* twoSum(int* numbers, int numbersSize, int target, int* returnSize) {
int i = 0;
int j = numbersSize - 1;
int* result = (int*)malloc(2 * sizeof(int));
while(i < j) {
int sum = numbers[i] + numbers[j];
if(sum > target) {
--j;
} else if(sum < target) {
++i;
} else {
result[0] = i + 1;
result[1] = j + 1;
*returnSize = 2;
return result;
}
}
*returnSize = 0;
return NULL;
}
public class Solution {
public int[] TwoSum(int[] numbers, int target) {
int i = 0;
int j = numbers.Length - 1;
while(i < j) {
int sum = numbers[i] + numbers[j];
if(sum > target) {
--j;
} else if(sum < target) {
++i;
} else {
return new int[] { i + 1, j + 1 };
}
}
return new int[] {};
}
}
