输入一个已经按升序排序过的数组和一个数字，在数组中查找两个数，使得它们的和正好是输入的那个数字。要求时间复杂度是o(n)。如果有多对数字的和等于输入的数字，输出任意一对即可。

可以使用双指针法来解决这个问题。定义两个指针，一个指向数组的第一个元素，一个指向数组的最后一个元素。如果两个指针指向的元素之和等于输入的数字，则直接返回这两个元素；如果两个指针指向的元素之和小于输入的数字，则将左指针向右移动一位；如果两个指针指向的元素之和大于输入的数字，则将右指针向左移动一位。重复以上步骤，直到找到两个元素之和等于输入的数字或者左指针大于等于右指针为止。

时间复杂度为O(n)，因为每个元素最多被访问一次。

相关问题

C++输入一个已经按升序排序过的数组和一个数字，在数组中查找两个数，使得它们的和正好是输入的那个数字

思路：

1. 定义左右指针，分别指向数组的第一个元素和最后一个元素。
2. 当左指针小于右指针时，执行以下循环：
1. 如果左右指针所指元素之和等于目标数字，返回左右指针所指元素的下标。
2. 如果左右指针所指元素之和小于目标数字，将左指针向右移动一位。
3. 如果左右指针所指元素之和大于目标数字，将右指针向左移动一位。
3. 如果数组中不存在符合条件的数，返回-1。

代码实现：

int* findNumbersWithSum(int* nums, int numsSize, int target, int* returnSize){
    int left = 0, right = numsSize - 1;
    while (left < right) {
        int sum = nums[left] + nums[right];
        if (sum == target) {
            int* result = (int*)malloc(2 * sizeof(int));
            result[0] = nums[left];
            result[1] = nums[right];
            *returnSize = 2;
            return result;
        } else if (sum < target) {
            left++;
        } else {
            right--;
        }
    }
    *returnSize = 0;
    return NULL;
}

时间复杂度：$O(n)$

空间复杂度：$O(1)$

输入一个已经按升序排序过的数组和一个数字,在数组中查找两个数,使得它们的和正好是输入的那个数字。C语言

可以使用双指针的方法来解决这个问题，设置一个指向数组起点的指针left和一个指向数组终点的指针right。如果left和right指向所指元素的和小于输入的目标数字，则将left向右移动一位；如果和大于目标数字，则将right向左移动一位；否则，返回left和right所指元素的下标即可。

以下是C语言代码实现：

#include <stdio.h>

void findSum(int arr[], int target, int length) {
    int left = 0, right = length - 1;
    while (left < right) {
        if (arr[left] + arr[right] == target) {
            printf("找到了两个数，它们的下标分别为 %d 和 %d \n", left, right);
            return;
        } else if (arr[left] + arr[right] < target) {
            left++;
        } else {
            right--;
        }
    }
    printf("没有找到符合要求的数对！\n");
}

int main() {
    int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
    int target = 10;
    int length = sizeof(arr) / sizeof(int);
    findSum(arr, target, length);
    return 0;
}

输出结果为：

找到了两个数，它们的下标分别为 0 和 8