双指针

题目

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

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

说明

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

示例：

输入: numbers = [2, 7, 11, 15], target = 9
输出: [1,2]
解释: 2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。

题解

思路

采用双指针思想，左指针指向最小元素，右指针指向最大元素

  • 相等时，直接返回
  • 两者指向和大于目标值，右指针向左移动
  • 两者指向和小于目标值，左指针向右移动
1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def twoSum(self, numbers, target): # numbers:list[int] ,target:int
        l=0
        r=len(numbers)-1
        while l<r:
            if numbers[l]+numbers[r]==target:
                return l+1,r+1
            if numbers[l]+numbers[r]>target:
                r=r-1
            if numbers[l]+numbers[r]<target:
                l=l+1
1
2
3
4
5
numbers = [2, 7, 11, 15]
target = 9
a= Solution()
result = a.twoSum(numbers,target)
print(result)
(1, 2)

博客内容遵循 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议

本文永久链接是：https://fishni.github.io/2021/01/24/LeetCode-E-%E5%8F%8C%E6%8C%87%E9%92%88-167.%20%E4%B8%A4%E6%95%B0%E4%B9%8B%E5%92%8C%20II%20-%20%E8%BE%93%E5%85%A5%E6%9C%89%E5%BA%8F%E6%95%B0%E7%BB%84/