
Problem Statement
The task involves an array of integers numbers
that is sorted in non-decreasing order. You are to find two distinct numbers in the array such that they sum up to a specific target
value. We denote these two numbers as numbers[index1]
and numbers[index2]
, where the position constraints are 1 <= index1 < index2 <= numbers.length
. The requirement is to return the indices of these two numbers, incremented by one to transform from a 0-based index to a 1-based index, resulting in a two-element array [index1, index2]
. It is guaranteed that there is one unique solution for the given input, and the solution must not use more than constant 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] <= 1000
numbers
is sorted in non-decreasing order.-1000 <= target <= 1000
- The tests are generated such that there is exactly one solution.
Approach and Intuition
Given the constraints and the problem requirements, a two-pointer technique is ideally suited for this problem for the following reasons:
The
numbers
array is already sorted. This sorting allows for an efficient approach where increasing and decreasing pointers can effectively find two numbers that sum to a target.By initializing two pointers, one at the beginning (
left
pointer) and one at the end (right
pointer) of the array, we can adjust these pointers based on the sum of thenumbers[left]
andnumbers[right]
.The detailed steps involved with this approach are:
Initialize two pointers:
left
at the start (index 0) andright
at the end (indexnumbers.length - 1
).While the
left
pointer is less than theright
pointer:Calculate the sum of the numbers at the two pointers:
current_sum = numbers[left] + numbers[right]
.If
current_sum
is equal to thetarget
, return the indices of these numbers as[left + 1, right + 1]
(adjusted for 1-based indexing).If
current_sum
is less than the target, it implies that we need a larger sum. Thus, move theleft
pointer one step to the right (left++
) to increase the sum.If
current_sum
is more than the target, it implies that we need a smaller sum. Thus, move theright
pointer one step to the left (right--
) to decrease the sum.
This method leverages the sorted nature of the array to efficiently find the two numbers, ensuring the use of only constant extra space and linear time complexity.
Solutions
- C++
class Solution {
public:
vector<int> findTwoSum(vector<int>& nums, int target) {
int left = 0;
int right = nums.size() - 1;
while (left < right) {
int currentSum = nums[left] + nums[right];
if (currentSum == target) {
return {left + 1, right + 1};
} else if (currentSum < target) {
++left;
} else {
--right;
}
}
return {-1, -1}; // Return statement if no two sum solution is found.
}
};
This function, findTwoSum
, works with a sorted integer array to determine two elements that sum up to a specific target. Utilize a two-pointer technique to efficiently find these elements, where one pointer starts at the beginning (left) and the other at the end (right) of the array.
The process involves:
- Incrementing the left pointer when the sum of the numbers at both pointers is less than the target, suggesting the need for a larger sum.
- Decrementing the right pointer when their sum surpasses the target, indicating a smaller sum is required.
- On finding a match where the sum equals the target, the function returns the positions of these two numbers as a vector, adjusting for 1-based indexing (hence
left + 1
andright + 1
).
If no such pair exists in the array that meets the target sum, the function returns {-1, -1}
.
Ensure that this C++ code is understood to effectively apply the two-pointer method on sorted arrays for searching specific sums.
- Java
class Solution {
public int[] findTwoSum(int[] nums, int targetSum) {
int start = 0;
int end = nums.length - 1;
while (start < end) {
int currentSum = nums[start] + nums[end];
if (currentSum == targetSum) {
return new int[] { start + 1, end + 1 };
} else if (currentSum < targetSum) {
++start;
} else {
--end;
}
}
return new int[] { -1, -1 };
}
}
This article provides a solution to the problem of finding two indices in a sorted array whose values sum up to a specific target number. The solution uses Java, featuring a straightforward two-pointer approach to efficiently solve the problem.
In the provided Java method findTwoSum
, you work with a nums
array of integers and a targetSum
. Initialize two pointers: start
points to the beginning of the array and end
points to the last element. Use a loop to check combinations of numbers at these pointers:
- Calculate
currentSum
by adding the values at thestart
andend
pointers. - If
currentSum
matchestargetSum
, return the 1-based indices of these numbers. - If
currentSum
is less thantargetSum
, increment thestart
pointer to explore larger sums. - If
currentSum
is greater, decrement theend
pointer to explore smaller sums.
If no pairs are found that meet the criteria, return {-1, -1}
as an indication.
This technique ensures a time complexity of O(n) by eliminating the need for a nested loop, making it highly efficient for sorted arrays. The distinct focus on using two pointers allows exploiting the sorted nature of the array to skip unnecessary comparisons, contributing to the overall efficiency of the algorithm.
- C
int* findTwoSum(int* nums, int numsLength, int targetSum, int* outputSize) {
int start = 0;
int end = numsLength - 1;
*outputSize = 2;
while (start < end) {
int currentSum = nums[start] + nums[end];
if (currentSum == targetSum) {
int* solution = malloc((*outputSize) * sizeof(int));
solution[0] = start + 1;
solution[1] = end + 1;
return solution;
} else if (currentSum < targetSum) {
start++;
} else {
end--;
}
}
int* solution = malloc((*outputSize) * sizeof(int));
solution[0] = -1;
solution[1] = -1;
return solution;
}
The given solution in C aims to find two numbers from a sorted array such that their sum equals a specified target number. Here is a concise summary of how the function operates:
- Initialize two pointers,
start
to the beginning of the array andend
to the last element. - Use a while loop to continue processing as long as
start
is less thanend
. - Calculate the sum of the elements at the
start
andend
indexes. - Compare the calculated sum with the target:
- If they match, allocate memory for a result array, store the 1-based positions of the elements, and return the array.
- If the calculated sum is less than the target, increment the
start
pointer to move right, thus increasing the sum. - If the calculated sum is greater than the target, decrement the
end
pointer to move left, thus decreasing the sum.
- If no matching elements are found by the time the loop exits, allocate memory for the result array, set both elements to -1 indicating no solution, and return the array.
This approach efficiently utilizes the properties of a sorted array to find the solution in linear time, making it optimal for larger data sets.
- JavaScript
var findTwoSum = function (nums, goal) {
let start = 0;
let end = nums.length - 1;
while (start < end) {
let currentSum = nums[start] + nums[end];
if (currentSum == goal) {
return [start + 1, end + 1];
} else if (currentSum < goal) {
start++;
} else {
end--;
}
}
return [-1, -1];
};
The provided JavaScript function, findTwoSum
, effectively solves the problem of finding two numbers in a sorted array that add up to a specific target, known as goal
. The implementation utilizes a two-pointer technique to efficiently search for the required pair. Here’s a closer look at how the solution works:
Initialize two pointers,
start
at the beginning (0-index) of the array andend
at the last index.Use a
while
loop to iterate through the array as long asstart
is less thanend
.Calculate the sum of the numbers pointed by the
start
andend
pointers.If the sum equals the goal, return the indices of the two numbers adjusted by 1 (to change from 0-based to 1-based index).
If the sum is less than the goal, increment the
start
pointer to increase the sum.If the sum is greater than the goal, decrement the
end
pointer to decrease the sum.If no pair is found by the end of the loop, return
[-1, -1]
indicating no solution.
This method is optimal for sorted arrays and runs with a time complexity of O(n), where n is the number of elements in the input array. Adjusting the pointers based on the comparison of the current sum and the goal allows the method to skip unnecessary elements, which results in the linear time complexity.
- Python
class Solution:
def findTwoSum(self, nums: List[int], goal: int) -> List[int]:
left = 0
right = len(nums) - 1
while left < right:
current_sum = nums[left] + nums[right]
if current_sum == goal:
return [left + 1, right + 1]
elif current_sum < goal:
left += 1
else:
right -= 1
return [-1, -1]
This guide walks through a solution for finding two numbers in a sorted array that sum up to a specific target. This Python solution uses a two-pointer technique to identify the indices of the two numbers.
- Initialize two pointers,
left
starting at the beginning of the array andright
at the end. - Iterate through the array using a while loop until
left
is less thanright
.- Calculate
current_sum
of the elements at theleft
andright
pointers. - If
current_sum
matches thegoal
, return the 1-based indices of these elements as a list[left + 1, right + 1]
. - If
current_sum
is less than thegoal
, increment theleft
pointer to explore higher sums. - If
current_sum
is greater than thegoal
, decrement theright
pointer to explore lower sums.
- Calculate
- If no suitable pair is found by the time the while loop exits, return
[-1, -1]
to indicate failure.
This method efficiently leverages the sorted nature of the array, achieving a time complexity of O(n) by eliminating the need for a nested loop.
No comments yet.