Leetcode 167. Two Sum II - Input Array Is Sorted

###### tags: `Array` <h1> Leetcode 167. Two Sum II - Input Array Is Sorted </h1> <ol> <li>問題描述</li> 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]. <li>Input的限制</li> <ul> <li>2 <= numbers.length <= 3 * 10^4</li> <li>-1000 <= numbers[i] <= 1000</li> <li>numbers is sorted in non-decreasing order.</li> <li>-1000 <= target <= 1000</li> <li>The tests are generated such that there is exactly one solution.</li> </ul> <li>思考流程</li> <ul> <li>Two Pointers</li> 對於要找到 2 個 array 元素相加等於 target 的目的來說，相加起來可能大於、小於或等於 target 值。因為 input array 已經排序好，所以當相加值不等於 target 值時，我們就可以依據指標的前進後退來更接近我們的 target 值。 首先，產生有 lo & hi 兩個指標，lo 指向 array 的最左邊；hi 指向 array 的最右邊。當 array[lo] + array[hi] 的結果大於 target，我們就把 hi 往左移動；若結果小於 0，則把 lo 往右移動。當發現結果等於 0，就找到我們的目標元素組合，回傳 lo+1, hi+1 作為回傳值。 最差的情況是兩個指標會互相交會，遍歷整個 array，故 time complexity 是 O(N)。除了 return list 之外，只使用到了 lo & hi 這兩個指標，故 space complexity 是 O(1)。 Time Complexity: O(N); Space Complexity: O(1) </ul> <li>測試</li> <ul> <li>test 1</li> Input: nums = [0, 1, 2, 3], target = 5 Output: [3, 4] <li>test 2( edge case )</li> 若 input array 找不到 target 值，則回傳錯誤訊息。 </ol>