输入一个已经按升序排序过的数组和一个数字,在数组中查找两个数,使得它们的和正好是输入的那个数字。要求时间复杂度是O(n)。如果有多对数字的和等于输入的数字,输出任意一对即可。用C语言编程
时间: 2024-05-24 22:10:38 浏览: 11
#include <stdio.h>
void findSum(int arr[], int n, int target) {
int left = 0, right = n - 1;
while (left < right) {
int sum = arr[left] + arr[right];
if (sum == target) {
printf("%d %d\n", arr[left], arr[right]);
return;
} else if (sum < target) {
left++;
} else {
right--;
}
}
printf("No such pair found.\n");
}
int main() {
int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
int n = sizeof(arr) / sizeof(arr[0]);
int target = 10;
findSum(arr, n, target);
return 0;
}
相关问题
C++输入一个已经按升序排序过的数组和一个数字,在数组中查找两个数,使得它们的和正好是输入的那个数字
思路:
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)$
输入一个已经按升序排序过的数组和一个数字,在数组中查找两个数,使得它们的和正好是输入的那个数字。C语言
可以使用双指针的方法来解决这个问题,设置一个指向数组起点的指针left和一个指向数组终点的指针right。如果left和right指向所指元素的和小于输入的目标数字,则将left向右移动一位;如果和大于目标数字,则将right向左移动一位;否则,返回left和right所指元素的下标即可。
以下是C语言代码实现:
```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
```
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)