接外包,有相关需求的可以联系我:Telegram | Email

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

该文章创建(更新)于02/22/2022,请注意文章的时效性!

描述

给你一个下标从 1 开始的整数数组 numbers ,该数组已按 非递减顺序排列 ,请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index1] 和 numbers[index2] ,则 1 <= index1 < index2 <= numbers.length 。

以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1 和 index2。

你可以假设每个输入 只对应唯一的答案 ,而且你 不可以 重复使用相同的元素。

你所设计的解决方案必须只使用常量级的额外空间。

思路

二分查找,快慢指针

Code

  • Submit Code
class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        slow = 0
        fast = len(numbers) - 1

        while(slow < fast):
            sum = numbers[slow] + numbers[fast]

            if(sum == target):
                return [slow + 1,fast + 1]
            elif(sum < target):
                slow += 1
            elif(sum > target):
                fast -= 1
  • Full Code
class Solution:
    def twoSum(self, numbers, target):
        slow = 0
        fast = len(numbers) - 1

        result = []

        while(slow < fast):
            print("slow" + str(numbers[slow])  + "\tfast" + str(numbers[fast]))
            sum = numbers[slow] + numbers[fast]
            if(sum == target):
                return ([slow+1,fast+1])
                result.append(slow+1)
                result.append(fast+1)
                # return result
            elif(sum < target):
                slow += 1
            elif(sum > target):
                fast -= 1


S = Solution()
In = [2,7,11,15]
target = 9
print(S.twoSum(In,target))


👇 Share | 分享 👇


要不赞赏一下?

微信
支付宝
PayPal
Bitcoin

版权声明 | Copyright

除非特别说明,本博客所有作品均采用知识共享署名-非商业性使用-禁止演绎 4.0 国际许可协议进行许可。转载请注明转自-
https://www.emperinter.info/2022/02/22/two-sum-ii-input-array-is-sorted/


要不聊聊?

我相信你准备留下的内容是经过思考的!【勾选防爬虫,未勾选无法留言】

*

*



微信公众号

👉 NewsLetter ❤️ 邮箱订阅 👈

优惠码