共计 1022 个字符,预计需要花费 3 分钟才能阅读完成。
167. 两数之和 II – 输出有序数组
题目起源:力扣(LeetCode)
https://leetcode-cn.com/problems/two-sum-ii-input-array-is-sorted
题目
给定一个已依照升序排列 的有序数组,找到两个数使得它们相加之和等于指标数。
函数应该返回这两个下标值 index1
和 index2
,其中 index1
必须小于 index2
。
阐明:
- 返回的下标值(
index1
和index2
)不是从零开始的。 - 你能够假如每个输出只对应惟一的答案,而且你不能够重复使用雷同的元素。
示例:
输出: numbers = [2, 7, 11, 15], target = 9
输入: [1,2]
解释: 2 与 7 之和等于指标数 9。因而 index1 = 1, index2 = 2。
解题思路
思路:双指针
先审题,首先题目中所给的数组是有序的,因为这个前提,咱们能够思考应用双指针的思路,放大范畴,进而求得答案。
这里,先留神题目中所给出的要求:
- 返回的下标值,并不是从零开始,而是从 1 开始
- 题目有惟一解,所以求得答案可间接返回。
当初说下算法的具体思路:
- 定义双指针
left, right
,别离指向有序数组的首尾; -
令两个指针所对应的数字相加,设为
two_sum
,与target
进行比拟:- 若
two_sum == target
,返回[left + 1, right + 1]
( 因为返回下标值从 1 开始 ) - 若
two_sum > target
,则向前挪动右指针; - 若
two_sum < target
,则向后挪动左指针。
- 若
算法实现的过程如下图:
具体的代码实现如下。
代码实现
class Solution:
def twoSum(self, numbers: List[int], target: int) -> List[int]:
length = len(numbers)
# 定义双指针,别离指向数组首尾
left = 0
right = length - 1
while left < right:
# 令指针所对应的数字相加,与 target 作比拟
two_sum = numbers[left] + numbers[right]
# 相等时,返回索引值,因为下标从 1 开始计算,要相应 +1
if two_sum == target:
return [left + 1, right + 1]
# 两数之和大于 target,挪动右指针放大两数和
elif two_sum > target:
right -= 1
# 两数和小于 target,挪动左指针增大两数和
else:
left += 1
return None
实现后果
欢送关注
公众号【书所集录】
正文完