167. Two Sum II - Input Array Is Sorted

題目 / Problem

中文： 給定一個 1-indexed（從 1 開始計算索引）的整數陣列 numbers，它已經 以非遞減順序排序。請找出兩個數，使它們的和等於指定的 target。設這兩個數為 numbers[index1] 和 numbers[index2]，其中 1 <= index1 < index2 <= numbers.length。

回傳這兩個數的索引 index1 和 index2（每個都加 1），形式為一個長度為 2 的整數陣列 [index1, index2]。

題目保證 恰好只有一組解，且 同一個元素不可使用兩次。你的解法 只能使用常數額外空間。

English: Given a 1-indexed integer array numbers that is already sorted in non-decreasing order, find two numbers that add up to a specific target. Let them be numbers[index1] and numbers[index2] with 1 <= index1 < index2 <= numbers.length. Return [index1, index2] (each incremented by one). There is exactly one solution, and you may not use the same element twice. Your solution must use only constant extra space.

Constraints: - 2 <= numbers.length <= 3 * 10^4 - -1000 <= numbers[i] <= 1000 - numbers is sorted in non-decreasing order - -1000 <= target <= 1000

Example:

Input:  numbers = [2, 7, 11, 15], target = 9
Output: [1, 2]
Explanation: 2 + 7 = 9, so the (1-indexed) positions are 1 and 2.

名詞解釋 / Glossary

• Sorted array / 已排序陣列：元素按照大小順序排列（這題是由小到大，允許重複）。Elements are arranged in order (here, non-decreasing — duplicates allowed).
• 1-indexed / 1 為起始索引：索引從 1 開始計算，而不是程式語言常見的 0。例如第一個元素的索引是 1。Indices start at 1 instead of the usual 0; the first element sits at index 1.
• Two pointers / 雙指針：一種常用技巧，使用兩個索引（通常一左一右）同時掃描陣列，根據條件移動其中一個來縮小搜尋範圍。A technique that keeps two indices (often one at each end) and moves one inward based on a comparison to shrink the search space.
• Brute force / 暴力解法：列舉所有可能組合的直接做法。在這題就是雙層迴圈試所有配對。Try every possible pair with nested loops — correct but slow.
• Time complexity O(n) / 時間複雜度 O(n)：執行時間隨輸入大小 n 線性成長。Runtime grows linearly with the input size n.
• In-place / 原地（常數空間）：演算法只使用固定數量的額外變數，不隨輸入大小成長。Uses only a fixed amount of extra memory regardless of input size.
• Invariant / 不變式：在演算法執行過程中始終為真的條件，用來證明演算法的正確性。A condition that always holds throughout execution — used to reason about correctness.

思路

暴力解法是用兩層迴圈枚舉所有 (i, j) 配對，檢查 numbers[i] + numbers[j] == target，這是 O(n²) 的時間，對於 n 高達 3 萬的輸入會慢到不能接受。我們可以用雜湊表把時間降到 O(n)，但這需要 O(n) 的額外空間，而題目要求 常數空間。關鍵觀察是：陣列已經排好序，這是非常強的條件，我們應該善加利用。設兩個指針 left = 0、right = n - 1，分別指向最小和最大的元素，計算 sum = numbers[left] + numbers[right]：如果 sum == target，找到答案；如果 sum < target，代表目前的和太小，因為陣列已排序，唯一能讓和變大的方式是把 left 往右移（換成更大的數），所以 left++；反之如果 sum > target，把 right 往左移，right--。這個過程保證了一個不變式：被排除的那一端的元素，跟剩下範圍內的任何元素配對都不可能等於 target，所以可以安全捨棄。每次迭代要嘛找到答案，要嘛縮小搜尋範圍一格，因此最多走 n 步，總時間 O(n)、空間 O(1)。

The brute-force approach tries every pair with nested loops in O(n²), which is too slow for n up to 30,000. A hash map drops the time to O(n) but uses O(n) extra space, violating the constant-space requirement. The crucial insight is that the array is already sorted — a powerful property we should exploit. Place two pointers, left at the smallest element and right at the largest, and look at sum = numbers[left] + numbers[right]. If sum == target, we're done. If sum < target, the sum is too small; since the array is sorted, the only way to increase it is to move left rightward to a larger value (moving right leftward would only decrease the sum). Symmetrically, if sum > target, move right leftward. This maintains the invariant that any pair we skip cannot possibly equal target, so discarding them is safe. Each step either finds the answer or shrinks the window by one, giving O(n) time and O(1) space.

逐步走查 / Walkthrough

Input: numbers = [2, 7, 11, 15], target = 9

注意我們從來沒檢查 (7, 11)、(7, 15)、(11, 15) 這些配對 — 雙指針法已經證明它們不可能是答案。 We never had to examine pairs like (7, 11), (7, 15), or (11, 15) — the two-pointer logic proves none of them can be the answer.

Solution — C

/*
 * 演算法 / Algorithm:
 * 雙指針法：因為陣列已排序，從兩端往中間夾。
 * sum 太小就把左指針右移（換更大的數），sum 太大就把右指針左移。
 * Two pointers: since the array is sorted, squeeze inward from both ends.
 * If sum is too small, move left rightward; if too big, move right leftward.
 * Time O(n), Space O(1).
 */

#include <stdlib.h>  // 為了 malloc / for malloc

/*
 * LeetCode 的 C 介面要求：
 * - 回傳一個 int* 指向結果陣列
 * - 透過 returnSize 這個 out-parameter 告訴呼叫者陣列長度
 * LeetCode's C signature requires returning an int* and writing the result
 * length into the out-parameter returnSize.
 */
int* twoSum(int* numbers, int numbersSize, int target, int* returnSize) {
    // 結果一定是長度 2 的陣列 / The answer is always a 2-element array
    *returnSize = 2;

    // 在堆上配置 2 個 int 的空間，因為函式回傳後區域變數會消失
    // Allocate 2 ints on the heap; local arrays would be invalid after return.
    // sizeof(int) 是一個 int 佔的位元組數 / sizeof(int) is the byte size of an int.
    int* result = (int*)malloc(2 * sizeof(int));

    // 左指針：從陣列開頭（最小值）/ left pointer: array start (smallest value)
    int left = 0;
    // 右指針：從陣列結尾（最大值）/ right pointer: array end (largest value)
    int right = numbersSize - 1;

    // 當兩個指針還沒交錯就繼續搜尋
    // Keep searching while the pointers haven't crossed.
    while (left < right) {
        // numbers[left] 是讀取陣列的第 left 個元素（0-indexed）
        // numbers[left] reads the element at position left (0-indexed in C).
        int sum = numbers[left] + numbers[right];

        if (sum == target) {
            // 找到答案！題目要求 1-indexed，所以兩個索引各加 1
            // Found it! Problem asks for 1-indexed positions, so add 1 to each.
            result[0] = left + 1;
            result[1] = right + 1;
            // 立刻回傳，避免繼續執行迴圈
            // Return immediately to exit the loop.
            return result;
        } else if (sum < target) {
            // 和太小：唯一能增大的方法是把 left 往右移到更大的數
            // Sum too small: only way to increase it is to move left to a bigger value.
            left++;
        } else {
            // 和太大：把 right 往左移到更小的數
            // Sum too big: move right leftward to a smaller value.
            right--;
        }
    }

    // 題目保證一定有解，這裡理論上不會執行到，但 C 要求所有路徑都要有回傳值
    // Problem guarantees a solution exists; unreachable, but C requires a return on all paths.
    return result;
}

Solution — C++

/*
 * 演算法 / Algorithm:
 * 與 C 版本完全相同的雙指針法，但使用 STL 的 vector 容器。
 * Same two-pointer algorithm as the C version, but using STL's vector.
 * Time O(n), Space O(1) extra (output vector not counted).
 */

#include <vector>  // 為了 std::vector / for std::vector

class Solution {
public:
    // vector<int> 是 C++ 標準函式庫提供的動態陣列（可變長度的陣列）
    // vector<int> is C++'s standard dynamic array (resizable array).
    // 參數加 const& 表示「不會修改且不複製」，避免大陣列複製成本
    // const& means "won't modify, won't copy" — avoids copying the input vector.
    std::vector<int> twoSum(const std::vector<int>& numbers, int target) {
        // .size() 回傳元素個數，型別是 size_t（無號整數）
        // 轉成 int 以便和指針做減法不會有警告
        // .size() returns the count as size_t (unsigned); cast to int for safe arithmetic.
        int left = 0;
        int right = static_cast<int>(numbers.size()) - 1;

        // 主迴圈：兩指針未交錯就繼續 / Main loop: while pointers haven't crossed
        while (left < right) {
            // numbers[left] 用 operator[] 讀取元素，和 C 陣列語法一樣
            // numbers[left] uses operator[] — same indexing syntax as a C array.
            int sum = numbers[left] + numbers[right];

            if (sum == target) {
                // 用列表初始化 (brace-init) 直接建構並回傳 vector
                // 1-indexed 所以兩個都 + 1
                // Brace-initialize and return the vector directly; +1 for 1-indexing.
                return {left + 1, right + 1};
            } else if (sum < target) {
                // ++left 是前置遞增，等同於 left = left + 1
                // ++left is pre-increment, equivalent to left = left + 1.
                ++left;
            } else {
                // --right 把右指針往左移一格 / move right pointer one step left
                --right;
            }
        }

        // 題目保證有解，回傳空 vector 作為安全 fallback
        // Problem guarantees a solution; empty vector as an unreachable fallback.
        return {};
    }
};

複雜度 / Complexity

• Time: O(n) — 每次迴圈迭代要嘛 left++ 要嘛 right--，所以兩指針之間的距離每次至少減 1。初始距離是 n - 1，因此最多迭代 n - 1 次。n 是陣列長度。Each iteration moves either left rightward or right leftward by 1, so the gap between them shrinks by 1 every step; with initial gap n - 1, the loop runs at most n - 1 times. n is the array length.
• Space: O(1) — 只使用了 left、right、sum 等固定數量的變數，沒有隨輸入大小成長的額外資料結構（C 版本配置的 2-int 輸出陣列是 LeetCode 介面要求的固定大小，不算在內）。Only a constant number of variables (left, right, sum) — no auxiliary data structures that grow with input size.

Pitfalls & Edge Cases

• 0-indexed vs 1-indexed / 索引起始混淆：C/C++ 陣列從 0 開始，但題目要求回傳 1-indexed 索引，必須記得 +1。忘記加 1 是最常見的錯誤。LeetCode wants 1-based positions but our arrays are 0-based; forgetting the +1 is the most common slip.
• Using the same element twice / 重複使用同一元素：迴圈條件用 left < right（嚴格小於），不是 <=，這樣保證兩個指針永遠不會指向同一個位置。Using left < right (strict) instead of <= prevents pairing an element with itself.
• Negative numbers / 負數：-1000 <= numbers[i] <= 1000 包含負數，但雙指針邏輯完全不依賴正負，因為「排序」這個性質已經涵蓋所有情況。The two-pointer logic works unchanged for negatives because it relies only on the sorted order.
• Integer overflow / 整數溢位：numbers[i] 最大 1000，兩個相加最多 2000，遠在 int 範圍內，這題不必擔心。對於數值更大的問題要小心。Sums max out at 2000 — well within int. Worth noting for harder variants where you'd need long long.
• Why not binary search? / 為什麼不用二分搜尋？：對每個 i 二分搜尋 target - numbers[i] 是 O(n log n)，比 O(n) 雙指針慢。雙指針之所以更快，是因為它「攤銷」了搜尋成本——已經排除的元素永遠不會再看。Binary-searching for each complement is O(n log n); the two-pointer sweep is O(n) because each element is visited at most once.
• Forgetting to set *returnSize (C only) / C 版本忘記設定 *returnSize：LeetCode 的 C 評測會用 *returnSize 判斷輸出長度，沒設定會導致評測讀到隨機記憶體。LeetCode's C judge reads *returnSize to know the output length; leaving it unset causes undefined behavior.