---
# System prepended metadata

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

---

# Leetcode 167. Two Sum II - Input Array Is Sorted
[Leetcode 167. Two Sum II - Input Array Is Sorted]([leetcode_url](https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/description/)) (<font color=#FFB800>Medium</font> 61.1%)
<!-- 
(<font color=#00AF9B>Easy</font> 53.8%) 
(<font color=#FFB800>Medium</font> 39.6%)
(<font color=#FF375F>Hard</font>)
 -->
    
- 限制 :
    > 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.

- Solution
    就是要一個指標從最前面，另外一個指標要在最後面，如果相加 > target ，就要讓後面的往前移一格，反之則前面的往後移一格，直到找到為止。
    - 時間複雜度: $O(n)$
    - 空間複雜度: $O(1)$

- 程式碼
    ```c++=
    class Solution {
    public:
        vector<int> twoSum(vector<int>& numbers, int target) {
            int left_index = 0, right_index = numbers.size() - 1;
            while(left_index < right_index)
            {
                int sum = numbers[left_index] + numbers[right_index];
                if(sum == target) return vector<int>{left_index + 1, right_index + 1};
                else if(sum < target) left_index++;
                else right_index--;
            }
            return vector<int>{1, 1};
        }
    };
    ```
