167. Two Sum II - Input Array Is Sorted Medium

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.

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

Approach

Input: An integer array numbers, a target value target

Output: Find two values whose sum equals target, and return their indices

This is an opposite-direction two pointers problem.

We can use a pair of opposite-direction two pointers to continuously find the combination whose sum is target.

When the sum is greater than target, move the right pointer; conversely, move the left pointer until the answer position is found. Note that the subscript starts from 1, so [left + 1, right + 1] should be returned.

Implementation

python

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        # Initialize left and right pointers
        left, right = 0, len(numbers) - 1

        # Continue searching while the left pointer is less than the right pointer
        while left < right:
            # The sum of the numbers pointed to by the current two pointers
            s = numbers[left] + numbers[right]

            if s > target:
                # If the sum is greater than the target value, the right number is too large, move the right pointer left
                right -= 1
            elif s < target:
                # If the sum is less than the target value, the left number is too small, move the left pointer right
                left += 1
            else:
                # Target combination found, return indices (problem requires 1-based indexing)
                return [left + 1, right + 1]

javascript

/**
 * @param {number[]} numbers
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(numbers, target) {
    let left = 0;
    let right = numbers.length - 1;

    while (left < right) {
        const s = numbers[left] + numbers[right];

        if (s > target) {
            right --;
        } else if (s < target) {
            left ++;
        } else {
            return [left + 1, right + 1];
        }
    }
};

Complexity Analysis

• Time Complexity: O(n)
• Space Complexity: O(1)

Links

167. Two Sum II - Input Array Is Sorted (English)167. 两数之和 II - 输入有序数组 (Chinese)