输入一个已经按升序排序过的数组和一个数字,在数组中查找两个数,使得它们的和正好是输入的那个数字。要求时间复杂度是O(n)。如果有多对数字的和等于输入的数字,输出任意一对即可。 【输入形式】 一个升序排序的数组以空格隔开,以及一个目标数字,换行输入
时间: 2024-02-27 12:53:48 浏览: 44
直接插入排序,快速排序,归并排序,堆排序,基数排序,计数排序。
好的,这是一个经典的双指针问题。我们可以用两个指针分别指向数组的头和尾,然后每次判断这两个指针所指的数的和与目标数字的大小关系,如果和小于目标数字,则左指针向右移动一位;如果和大于目标数字,则右指针向左移动一位;如果和等于目标数字,则找到了一对数字,直接返回即可。
以下是代码实现:
```python
def find_numbers(nums, target):
left, right = 0, len(nums) - 1
while left < right:
s = nums[left] + nums[right]
if s < target:
left += 1
elif s > target:
right -= 1
else:
return nums[left], nums[right]
return None
```
其中,`nums`是输入的升序排序数组,`target`是目标数字。函数返回找到的一对数字,如果不存在则返回`None`。时间复杂度是$O(n)$,因为最多只需要遍历一遍数组。
阅读全文