167. Two Sum II - Input Array Is Sorted

題目描述

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

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

題目限制

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

解題思路

由於陣列已經排序，我們可以利用 雙指標（Two Pointers）的方法來解決此問題。設定兩個指標 left 和 right，分別指向陣列的開頭和結尾，進行以下操作：

1. 計算當前總和：sum = numbers[left] + numbers[right]。
2. 比較與目標值的關係：
   • 如果 sum == target：找到目標，返回 [left + 1, right + 1]（因為索引以 1 為基準）。
   • 如果 sum < target：總和太小，為了增大總和，需要將左指標右移一位（left++）。
   • 如果 sum > target：總和太大，為了減小總和，需要將右指標左移一位（right--）。
3. 迭代：重複上述步驟，直到找到符合條件的兩個數字。

透過上述操作，可以在 O(n) 的時間內找到符合條件的兩個數字，並且只使用 O(1) 的額外空間。

程式碼

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 {};
    }
};

時間與空間複雜度分析

• 時間複雜度：O(n)
  • 分析：指標 left 和 right 在陣列上移動，每次迭代至少移動一個指標，因此最多進行 n 次操作，時間複雜度為 O(n)。
• 空間複雜度：O(1)
  • 分析：除了使用固定數量的變數（如 left、right、sum）外，沒有使用與輸入大小相關的額外空間。