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

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

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

题目大意 #

给定一个升序排列的整数数组:numbers 和一个目标值 target

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

注意:数组下标从 1 开始计数。

解题思路 #

这道题如果暴力遍历数组,从中找到相加之和等于 target 的两个数,时间复杂度为 O(n^2),可以尝试一下。

1
2
3
4
5
6
7
8
class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        size = len(numbers)
        for i in range(size):
            for j in range(i + 1, size):
                if numbers[i] + numbers[j] == target:
                    return [i + 1, j + 1]
        return [-1, -1]

结果不出意外的超时了。所以我们要想办法减少时间复杂度。

因为数组是有序的,所以我们可以考虑使用双指针来减少时间复杂度。具体做法如下:

  • 使用两个指针 leftrightleft 指向数组第一个值最小的元素位置,right 指向数组值最大元素位置。
  • 判断两个位置上的元素的和与目标值的关系。
    • 如果元素和等于目标值,则返回两个元素位置。
    • 如果元素和大于目标值,则让 right 左移,继续检测。
    • 如果元素和小于目标值,则让 left 右移,继续检测。
  • 直到 leftright 移动到相同位置停止检测。
  • 如果最终仍没找到,则返回 [-1, -1]

代码 #

 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]:
        left = 0
        right = len(numbers) - 1
        while left < right:
            total = numbers[left] + numbers[right]
            if total == target:
                return [left + 1, right + 1]
            elif total < target:
                left += 1
            else:
                right -= 1
        return [-1, -1]
本站总访问量  次  |  您是本站第  位访问者