/*
 * 演算法 / 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;
}