Description

167. Two Sum II - Input Array Is Sorted

Given a 1-indexed array of integers numbers that is already sorted in non-decreasing order, find two numbers such that they add up to a specific target number. Let these two numbers be numbers[index1] and numbers[index2] where 1 <= index1 < index2 <= numbers.length.

Return the indices of the two numbers, index1 and index2, added by one as an integer array [index1, index2] of length 2.

The tests are generated such that there is exactly one solution. You may not use the same element twice.

Your solution must use only constant extra space.

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

Constraints:

2 <= numbers.length <= 3 * 10^4
-1000 <= numbers[i] <= 1000
numbers is sorted in non-decreasing order.
-1000 <= target <= 1000
The tests are generated such that there is exactly one solution.

Answer & Explaining

int* twoSum(int* numbers, int numbersSize, int target, int* returnSize) {
    int left = 0; // 左指針初始化，指向陣列開頭
    int right = numbersSize - 1; // 右指針初始化，指向陣列尾端

    // 分配結果的記憶體空間
    int* result = (int*)malloc(2 * sizeof(int)); 
    *returnSize = 2; // 設定回傳陣列的大小為 2

    // 當left pointer小於right pointer時進行
    while (left < right) {
        int sum = numbers[left] + numbers[right]; // 計算目前left, right pointer的和

        if (sum == target) { // 如果和等於target
            result[0] = left + 1; // 將left+1存至result[0]
            result[1] = right + 1; // 將right+1存至result[1]
            return result; // 返回result
        } else if (sum < target) { // 如果和小於target
            left++; // left++，使和變大
        } else { // 如果和大於target
            right--; // right--，使和減小
        }
    }
    return result; 
}

Testing

#include <stdio.h>
#include <stdlib.h>

int* twoSum(int* numbers, int numbersSize, int target, int* returnSize) {
    int left = 0; // 左指針初始化，指向陣列開頭
    int right = numbersSize - 1; // 右指針初始化，指向陣列尾端

    // 分配結果的記憶體空間
    int* result = (int*)malloc(2 * sizeof(int)); 
    *returnSize = 2; // 設定回傳陣列的大小為 2

    // 當left pointer小於right pointer時進行
    while (left < right) {
        int sum = numbers[left] + numbers[right]; // 計算目前left, right pointer的和

        if (sum == target) { // 如果和等於target
            result[0] = left + 1; // 將left+1存至result[0]
            result[1] = right + 1; // 將right+1存至result[1]
            return result; // 返回result
        } else if (sum < target) { // 如果和小於target
            left++; // left++，使和變大
        } else { // 如果和大於target
            right--; // right--，使和減小
        }
    }
    return result; 
}

int main() {
    // 測試案例
    int numbers1[] = {2, 7, 11, 15}; // 測試陣列 1
    int target1 = 9; // 測試目標 1
    int returnSize1; // 返回大小變數
    int* result1 = twoSum(numbers1, 4, target1, &returnSize1); // 調用 twoSum 函數
    printf("Test 1: [%d, %d]\n", result1[0], result1[1]); // 輸出測試結果
    free(result1); // 釋放分配的內存

    int numbers2[] = {2, 3, 4}; // 測試陣列 2
    int target2 = 6; // 測試目標 2
    int returnSize2; // 返回大小變數
    int* result2 = twoSum(numbers2, 3, target2, &returnSize2); // 調用 twoSum 函數
    printf("Test 2: [%d, %d]\n", result2[0], result2[1]); // 輸出測試結果
    free(result2); // 釋放分配的內存

    int numbers3[] = {-1, 0}; // 測試陣列 3
    int target3 = -1; // 測試目標 3
    int returnSize3; // 返回大小變數
    int* result3 = twoSum(numbers3, 2, target3, &returnSize3); // 調用 twoSum 函數
    printf("Test 3: [%d, %d]\n", result3[0], result3[1]); // 輸出測試結果
    free(result3); // 釋放分配的內存

    return 0; // 返回 0，表示程式正常結束
}