C语言输入一个已经按升序排序过的数组和一个数字,在数组中查找两个数,使得它们的和正好是输入的那个数字。要求时间复杂度是O(n)。如果有多对数字的和等于输入的数字,输出任意一对即可。
时间: 2024-01-22 12:19:32 浏览: 87
可以使用双指针法来实现时间复杂度为O(n)的查找。定义两个指针left和right,分别指向数组的第一个元素和最后一个元素。如果left和right指向的两个元素的和大于输入的数字,则right指针左移,否则left指针右移。直到找到两个元素的和等于输入的数字为止。
以下是C语言的代码实现:
```
#include <stdio.h>
void findTwoNumbers(int arr[], int n, int target)
{
int left = 0, right = n - 1;
while (left < right)
{
if (arr[left] + arr[right] == target)
{
printf("找到一对数字: %d 和 %d\n", arr[left], arr[right]);
return;
}
else if (arr[left] + arr[right] < target)
{
left++;
}
else
{
right--;
}
}
printf("没有找到匹配的数字对\n");
}
int main()
{
int arr[] = {2, 3, 4, 6, 8, 9, 10};
int n = sizeof(arr) / sizeof(arr[0]);
int target = 13;
findTwoNumbers(arr, n, target);
return 0;
}
```
输出结果为:找到一对数字: 3 和 10。
阅读全文