LeetCode 167. 两数之和 II - 输入有序数组 | Python

167. 两数之和 II - 输入有序数组


题目来源:力扣(LeetCode)
https://leetcode-cn.com/problems/two-sum-ii-input-array-is-sorted

题目


给定一个已按照升序排列 的有序数组,找到两个数使得它们相加之和等于目标数。

函数应该返回这两个下标值 index1index2,其中 index1 必须小于 index2

说明:

  • 返回的下标值(index1index2)不是从零开始的。
  • 你可以假设每个输入只对应唯一的答案,而且你不可以重复使用相同的元素。

示例:

输入: 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,则向后移动左指针。

算法实现的过程如下图:

LeetCode 167. 两数之和 II - 输入有序数组 | Python

具体的代码实现如下。

代码实现


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

实现结果


LeetCode 167. 两数之和 II - 输入有序数组 | Python

欢迎关注


公众号 【书所集录