LeetCode 167. 两数之和 II - 输入有序数组 | Python
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
实现结果
欢迎关注
公众号 【书所集录】