Leetcode 167. Two Sum II - Input Array Is Sorted

Leetcode Top Interview 150 的其中一題

題目描述

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

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.

解法

這題另一種解法是一邊用 map 紀錄目前有的數值，每次都檢查 target-numbers[i] 這個值是否已經存在。但由於題目規定只能使用 constant extra space，所以以下解法使用雙指針。

func twoSum(numbers []int, target int) []int {
    left := 0
    right := len(numbers) - 1 

    for left < right {
        // 如果相加等於 target，回傳答案
        if numbers[left] + numbers[right] == target {
            return []int{left+1, right+1}
        }
        
        // 如果相加比 target 大，代表其中一個數字應該更小，將右指針左移
        if numbers[left] + numbers[right] > target {
            right--
        }
        
        // 如果相加比 target 小，代表其中一個數字應該更大，將左指針右移
        if numbers[left] + numbers[right] < target {
            left++
        }
    }

    return []int{1, 2}
}

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