167. Two Sum II - Input Array Is Sorted

題目描述

題目連結：167. Two Sum II - Input Array Is Sorted

給定一個已經排序的非嚴格遞增陣列 numbers 和一個目標值 target，需要在這個陣列中找到兩個數字，使它們的和等於 target。要求返回這兩個數字的索引（以1為基準）

題目限制

• 每個輸入只會有一個解
• 不可以使用同樣的元素兩次
• 你的解法必須只使用額外常數空間
• 你可以假設每組輸入只有一個解

解題思路

• 由於陣列已經排序，可以利用two pointers的方法來解決此問題。兩個pointer分別設置在陣列的頭和尾：
  1. 當 left pointer（i）右移，則和變大
  2. 當 right pointer（j）左移，則和變小
• 透過上述操作，可以不斷接近目標值 target，直到找到符合條件的兩個數字

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        const int n = numbers.size();
        int i = 0;
        int j = n - 1;
        while (i < j) {
            if (numbers[i] + numbers[j] == target) {
                return { i + 1, j + 1 };
            }

            if (numbers[i] + numbers[j] < target) {
                i += 1;
            } else {
                j -= 1;
            }
        }
        return {};
    }
};

複雜度分析

1. 時間複雜度：O(n)，由於每個元素最多只會被訪問一次，總共需要進行 n 次操作，因此時間複雜度為 O(n)
2. 空間複雜度：O(1)