167. Two Sum II - Input Array Is Sorted

題目：
給你一個 遞增排序 的整數陣列 numbers（索引從 1 開始），以及一個目標數字 target
要求找出 兩個數字 的和等於 target，並回傳這兩個數字的索引（1-based）

範例：

• 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].

想法：
利用迴圈一個一個加總

程式碼：

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        // 外層迴圈：固定第一個數字
        for (int i = 0; i < numbers.length - 1; i++) {
            // 內層迴圈：從 i+1 開始，去找能和 numbers[i] 湊成 target 的另一個數
            for (int j = i + 1; j < numbers.length; j++) {
                
                if (numbers[i] + numbers[j] == target) { // 檢查兩個數字的加總
                    return new int[]{i + 1, j + 1}; // 題目要求回傳 1-based index（從1開始數）
                }
            }
        }
        // 如果沒找到（題目保證一定有答案）
        return new int[]{-1, -1};
    }
}

實際操作：

numbers = [1, 3, 4, 5, 7, 10, 11]
target = 9

Step1:

• i = 0 (numbers[0] = 1)：
  • j = 1: 1 + 3 = 4 → 不等 → 繼續
  • j = 2: 1 + 4 = 5 → 不等
  • j = 3: 1 + 5 = 6 → 不等
  • j = 4: 1 + 7 = 8 → 不等
  • j = 5: 1 + 10 = 11 → 不等
  • j = 6: 1 + 11 = 12 → 不等
→ 外層 i=0 完成（都沒找到）

Step2:

• i = 1 (numbers[1] = 3)：
  • j = 2: 3 + 4 = 7 → 不等
  • j = 3: 3 + 5 = 8 → 不等
  • j = 4: 3 + 7 = 10 → 不等
  • j = 5: 3 + 10 = 13 → 不等
  • j = 6: 3 + 11 = 14 → 不等
→ 外層 i=1 完成

Step3:

• i = 2 (numbers[2] = 4)：
  • j = 3: 4 + 5 = 9 → 等於 target → 找到 → 回傳 {i+1, j+1} = {3, 4}
（此時程式結束，內層到 j=3 才找到）

結果：回傳 [3, 4]

GPT推薦：

想法：
由於陣列已經排序好，最簡單高效的方法是用 雙指標（Two Pointers）。

程式碼：

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int left = 0;                    // 左指標
        int right = numbers.length - 1;  // 右指標

        while (left < right) {
            int sum = numbers[left] + numbers[right];

            if (sum == target) {
                // 題目要求回傳 1-based index
                return new int[] {left + 1, right + 1};
            } else if (sum < target) {
                // 和太小 → 左指標右移，嘗試增加和
                left++;
            } else {
                // 和太大 → 右指標左移，嘗試減少和
                right--;
            }
        }

        // 題目保證有解，不會走到這裡
        return new int[] {-1, -1};
    }
}