Description
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].Solution in Python
Python
from typing import List
class Solution:
def twoSum(self, numbers: List[int], target: int) -> List[int]:
# Initialize two pointers, one at the start (left) and one at the end (right) of the list
left = 0
right = len(numbers) - 1
# Use a while loop to iterate until the left pointer is less than the right pointer
while left < right:
# Calculate the sum of the two elements pointed by the left and right pointers
current_sum = numbers[left] + numbers[right]
# If the sum is equal to the target, return the indices (1-based)
if current_sum == target:
return [left + 1, right + 1]
# If the sum is less than the target, move the left pointer to the right
elif current_sum < target:
left += 1
# If the sum is greater than the target, move the right pointer to the left
else:
right -= 1
# This line is never reached because the problem guarantees exactly one solution
return []Explanation
- Initialization:
leftpointer starts at the beginning of the list (left = 0).rightpointer starts at the end of the list (right = len(numbers) - 1).
- Iteration:
- A while loop runs as long as
leftis less thanright.
- A while loop runs as long as
- Sum Calculation:
- Calculate the sum of the elements at the
leftandrightpointers:current_sum = numbers[left] + numbers[right].
- Calculate the sum of the elements at the
- Comparison and Pointer Adjustment:
- If
current_sumis equal to thetarget, return the indices. Note that the indices need to be adjusted to be 1-based, hence the return statementreturn [left + 1, right + 1]. - If
current_sumis less than thetarget, it means we need a larger sum, so increment theleftpointer (left += 1). - If
current_sumis greater than thetarget, it means we need a smaller sum, so decrement therightpointer (right -= 1).
- If
- Guaranteed Solution:
- The problem guarantees that there is exactly one solution, so the while loop will always find and return the correct indices. Therefore, the return statement outside the loop is never actually reached.
Solution in Javascript
JavaScript
/**
* @param {number[]} numbers
* @param {number} target
* @return {number[]}
*/
var twoSum = function(numbers, target) {
// Initialize two pointers, one at the start (left) and one at the end (right) of the array
let left = 0;
let right = numbers.length - 1;
// Use a while loop to iterate until the left pointer is less than the right pointer
while (left < right) {
// Calculate the sum of the two elements pointed by the left and right pointers
let currentSum = numbers[left] + numbers[right];
// If the sum is equal to the target, return the indices (1-based)
if (currentSum === target) {
return [left + 1, right + 1];
}
// If the sum is less than the target, move the left pointer to the right
else if (currentSum < target) {
left++;
}
// If the sum is greater than the target, move the right pointer to the left
else {
right--;
}
}
// This line is never reached because the problem guarantees exactly one solution
return [];
};Solution in Java
Java
class Solution {
public int[] twoSum(int[] numbers, int target) {
// Initialize two pointers, one at the start (left) and one at the end (right) of the array
int left = 0;
int right = numbers.length - 1;
// Use a while loop to iterate until the left pointer is less than the right pointer
while (left < right) {
// Calculate the sum of the two elements pointed by the left and right pointers
int currentSum = numbers[left] + numbers[right];
// If the sum is equal to the target, return the indices (1-based)
if (currentSum == target) {
return new int[] {left + 1, right + 1};
}
// If the sum is less than the target, move the left pointer to the right
else if (currentSum < target) {
left++;
}
// If the sum is greater than the target, move the right pointer to the left
else {
right--;
}
}
// This line is never reached because the problem guarantees exactly one solution
return new int[] {};
}
}Solution in C#
C#
public class Solution {
public int[] TwoSum(int[] numbers, int target) {
// Initialize two pointers, one at the start (left) and one at the end (right) of the array
int left = 0;
int right = numbers.Length - 1;
// Use a while loop to iterate until the left pointer is less than the right pointer
while (left < right) {
// Calculate the sum of the two elements pointed by the left and right pointers
int currentSum = numbers[left] + numbers[right];
// If the sum is equal to the target, return the indices (1-based)
if (currentSum == target) {
return new int[] { left + 1, right + 1 };
}
// If the sum is less than the target, move the left pointer to the right
else if (currentSum < target) {
left++;
}
// If the sum is greater than the target, move the right pointer to the left
else {
right--;
}
}
// This line is never reached because the problem guarantees exactly one solution
return new int[] {};
}
}