昨天做的是簡單的 2 Sum，今天做一樣的問題，但是輸入的 Array 是經過排序的，而且要求只能額外使用固定的空間．這就表示我們無法再使用 Hashmap 去紀錄對應元素的index．因為 hashmap 的時間複雜度跟空間複雜度都是 O(n)．

問題

https://leetcode.com/problems/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 * 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.

解答

考慮到輸入的 array 是已經排序過的.我們可以額外宣告兩個指標，一個從前面往前搜尋，一個從後面往前搜尋，逐一比對及找尋和為目標值的兩個數值，將空間複雜度降為 O(1)

Python

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        i = 0
        j = len(nums)-1
        while i < j:
            sum = nums[i] + nums[j]
            if sum == target:
                return [i+1, j+1]
            elif sum < target:
                i = i + 1
            else:
                j = j - 1

Go

注意 Go 沒有 while 迴圈， 你必須用 for loop

for condition {
    // Code to repeatedly execute
}

func twoSum(numbers []int, target int) []int {
    i := 0
    j := len(numbers)-1
    for i < j {
        sum := numbers[i] + numbers[j]
        if sum == target {
            return []int{i+1, j+1}
        } else if sum < target {
            i = i + 1
        } else {
            j = j - 1
        }
    }
    return []int{}
    
}

感想

昨天的題目也可以先做排序在依照本題的做法來解，但這樣會增加時間複雜度．
所以在工作上要時時考慮輸入的資料量和實際的環境要求．