在排序数组中查找和为给定值的两个数字 ?
参考答案:
在排序数组中查找和为给定值的两个数字的问题,可以通过双指针法(Two Pointers)来解决。双指针法的基本思想是使用两个指针从数组的两端开始,向中间移动,比较两个指针所指向的元素之和与目标值的大小关系,以此来调整指针的移动方向。
以下是一个使用 Python 实现的示例:
def twoSum(numbers, target):
left = 0
right = len(numbers) - 1
while left < right:
current_sum = numbers[left] + numbers[right]
if current_sum == target:
return [left + 1, right + 1] # 返回的是索引,题目要求从1开始,所以加1
elif current_sum < target:
left += 1
else:
right -= 1
return None # 如果没有找到符合条件的两个数,返回 None
# 示例
numbers = [2, 7, 11, 15]
target = 9
print(twoSum(numbers, target)) # 输出: [1, 2]
在这个示例中,numbers
是排序后的数组,target
是要查找的目标和。函数 twoSum
返回的是数组中两个数的索引(从1开始),这两个数的和等于 target
。如果找不到这样的两个数,函数返回 None
。
这个算法的时间复杂度是 O(n),其中 n 是数组的长度。因为两个指针最多各移动一次,所以总的时间复杂度是线性的。