剑指 Offer II 006. 排序数组中两个数字之和

剑指 Offer II 006. 排序数组中两个数字之和 #

  • 标签:数组、双指针、二分查找
  • 难度:简单

题目大意 #

给定一个升序数组:numbers 和一个目标值 target

要求:从数组中找出满足相加之和等于 target 的两个数,并返回两个数在数组中下的标值。

解题思路 #

因为数组是有序的,所以我们可以使用两个指针 low,high。low 指向数组开始较小元素位置,high 指向数组较大元素位置。判断两个位置上的元素和,如果和等于目标值,则返回两个元素位置。如果和大于目标值,则 high 左移,继续检测。如果和小于目标值,则 low 右移,继续检测。直到 low 和 high 移动到相同位置停止检测。若最终仍没找到,则返回 [0, 0]。

代码 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        low = 0
        high = len(numbers) - 1
        while low < high:
            total = numbers[low] + numbers[high]
            if total == target:
                return [low, high]
            elif total < target:
                low += 1
            else:
                high -= 1
        return [0, 0]
本站总访问量  次  |  您是本站第  位访问者