Two Sum II - Input Array Is Sorted

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 and right + 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.

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 the start and end pointers.
• If currentSum matches targetSum, return the 1-based indices of these numbers.
• If currentSum is less than targetSum, increment the start pointer to explore larger sums.
• If currentSum is greater, decrement the end 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.

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 and end to the last element.
• Use a while loop to continue processing as long as start is less than end.
• Calculate the sum of the elements at the start and end 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.

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:

1. Initialize two pointers, start at the beginning (0-index) of the array and end at the last index.

2. Use a while loop to iterate through the array as long as start is less than end.

3. Calculate the sum of the numbers pointed by the start and end pointers.

4. 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).

5. If the sum is less than the goal, increment the start pointer to increase the sum.

6. If the sum is greater than the goal, decrement the end pointer to decrease the sum.

7. 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.

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 and right at the end.
• Iterate through the array using a while loop until left is less than right.
  • Calculate current_sum of the elements at the left and right pointers.
  • If current_sum matches the goal, return the 1-based indices of these elements as a list [left + 1, right + 1].
  • If current_sum is less than the goal, increment the left pointer to explore higher sums.
  • If current_sum is greater than the goal, decrement the right pointer to explore lower sums.
• 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.