---
# System prepended metadata

title: "\n    Leetcode 167. Two Sum II - Input Array Is Sorted\n"
tags: [Array]

---

###### 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.<br><br>

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.<br><br>
    
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>
    <br>
    
<li>思考流程</li>
    <ul>
        <li>Two Pointers</li>
        對於要找到 2 個 array 元素相加等於 target 的目的來說，相加起來可能大於、小於或等於 target 值。因為 input array 已經排序好，所以當相加值不等於 target 值時，我們就可以依據指標的前進後退來更接近我們的 target 值。<br><br>
        首先，產生有 lo & hi 兩個指標，lo 指向 array 的最左邊；hi 指向 array 的最右邊。當 array[lo] + array[hi] 的結果大於 target，我們就把 hi 往左移動；若結果小於 0，則把 lo 往右移動。當發現結果等於 0，就找到我們的目標元素組合，回傳 lo+1, hi+1 作為回傳值。
        <br>
        <br>
        最差的情況是兩個指標會互相交會，遍歷整個 array，故 time complexity 是 O(N)。除了 return list 之外，只使用到了 lo & hi 這兩個指標，故 space complexity 是 O(1)。
        <br>
        <br>
        Time Complexity: O(N); Space Complexity: O(1)
        <br><br>
    </ul>
<li>測試</li>
    <ul>
        <li>test 1</li>
        Input: nums = [0, 1, 2, 3], target = 5<br>
        Output: [3, 4]
        <li>test 2( edge case )</li>
        若 input array 找不到 target 值，則回傳錯誤訊息。
</ol>