167. Two Sum II - Input Array Is Sorted

題目敘述

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

Constraints:

• 2 <= numbers.length <= 3 * 10**4
• -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.

題目翻譯

給一維陣列的參數 numbers，找出兩個數加總是等於 target 的值，然後回傳其索引。如果沒有符合的就回傳 -1。其中索引的順序是從 1 開始算起的。

解法解析

使用單純的 Two pointers 解法

Time complexity: O(n) Space complexity: O(1)

解法範例

Go

func twoSum(numbers []int, target int) []int {
    var (
        low  int = 0
        high int = len(numbers) - 1
    )
    for low < high {
        total := numbers[low] + numbers[high]
        if total == target {
            return []int{low + 1, high + 1}
        }
        if total < target {
            low++
        } else {
            high--
        }
    }
    return []int{-1, -1}
}

JavaScript

/**
 * @param {number[]} numbers
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function (numbers, target) {
    let low = 0,
        high = numbers.length - 1;
    while (low < high) {
        const sum = numbers[low] + numbers[high];
        if (sum === target) {
            return [low + 1, high + 1];
        }
        if (sum < target) {
            low++;
        } else {
            high--;
        }
    }
    return [-1, -1];
};

Kotlin

class Solution {
    fun twoSum(numbers: IntArray, target: Int): IntArray {
        var low = 0
        var high = numbers.size - 1
        while (low < high) {
            val sum = numbers[low] + numbers[high]
            if (sum == target) {
                return intArrayOf(low + 1, high + 1)
            }
            if (sum < target) {
                low++
            } else {
                high--
            }
        }
        return intArrayOf(-1, -1)
    }
}

PHP

class Solution
{

    /**
     * @param Integer[] $numbers
     * @param Integer $target
     * @return Integer[]
     */
    function twoSum($numbers, $target)
    {
        $low = 0;
        $high = count($numbers) - 1;
        while ($low < $high) {
            $sum = $numbers[$low] + $numbers[$high];
            if ($sum == $target) {
                return [$low + 1, $high + 1];
            }
            if ($sum < $target) {
                $low++;
            } else {
                $high--;
            }
        }
        return [-1, -1];
    }
}

Python

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        low: int = 0
        high: int = len(numbers) - 1
        while low < high:
            total: int = numbers[low] + numbers[high]
            if total == target:
                return [low + 1, high + 1]
            if total < target:
                low += 1
            else:
                high -= 1
        return [-1, -1]

Rust

impl Solution {
    pub fn two_sum(numbers: Vec<i32>, target: i32) -> Vec<i32> {
        let mut low = 0;
        let mut high = numbers.len() - 1;
        while low < high {
            let sum = numbers[low]+numbers[high];
            if sum == target {
                return Vec::from([low as i32 + 1, high as i32 + 1]);
            }
            if sum < target {
                low+=1;
            } else {
                high-=1;
            }
        }
        return Vec::from([-1, -1]);
    }
}

Swift

class Solution {
    func twoSum(_ numbers: [Int], _ target: Int) -> [Int] {
        var low: Int = 0
        var high: Int = numbers.count - 1
        while low < high {
            let sum: Int = numbers[low] + numbers[high]
            if sum == target {
                return [low + 1, high + 1]
            }
            if sum < target {
                low += 1
            } else {
                high -= 1
            }
        }

        return [-1, -1]
    }
}