167. Two Sum II - Input Array Is Sorted

題目網址：https://leetcode.cn/problems/two-sum-ii-input-array-is-sorted/

題意：給一 index 從 1 開始的整數 array numbers, 該 array 已按照非遞減順序排列, 請從 numbers 中找出相加等於 target 的兩數之 index index1、index2, 其中 1 ≤ index1 ≤ index2 ≤ numbers.length。

假設每一種 target 只會對應到一組解, 且同一個元素不可重複使用。

請設計 $O(1)$ space 的演算法。

Solution：

想法：概念同 15. 3Sum, 由於 array 已排序, 故直接使用 Two Pointers 即可

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        int left = 0, right = numbers.size() - 1;

        while (left < right) {
            const int sum = numbers[left] + numbers[right];
            if (sum == target) {
                return {left + 1, right + 1};
            } else if (sum < target) {
                left++;
            } else {
                right--;
            }
        }
        return {};
    }
};

• time：$O(n)$ ➔ 遍歷 numbers
• space：$O(1)$ ➔ 只需常數空間