欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

两数之和 -- 输入有序数组 | Python

程序员文章站 2022-05-25 09:50:45
使用双指针的思路,解决LeetCode 《167. 两数之和 II - 输入有序数组》问题...

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

算法实现的过程如下图:

两数之和 -- 输入有序数组 | 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

实现结果


两数之和 -- 输入有序数组 | Python

欢迎关注


公众号 【书所集录

本文地址:https://blog.csdn.net/weixin_45642918/article/details/107469572