C++输入一个已经按升序排序过的数组和一个数字,在数组中查找两个数,使得它们的和正好是输入的那个数字
时间: 2024-04-29 10:23:21 浏览: 96
思路:
1. 定义左右指针,分别指向数组的第一个元素和最后一个元素。
2. 当左指针小于右指针时,执行以下循环:
1. 如果左右指针所指元素之和等于目标数字,返回左右指针所指元素的下标。
2. 如果左右指针所指元素之和小于目标数字,将左指针向右移动一位。
3. 如果左右指针所指元素之和大于目标数字,将右指针向左移动一位。
3. 如果数组中不存在符合条件的数,返回-1。
代码实现:
```c
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)$
阅读全文