【LeetCode最详尽解答】167-两数之和 II-输入有序数组 Two-Sum-II-Input-Array-Is-Sorted

欢迎收藏Star我的Machine Learning Blog:https://github.com/purepisces/Wenqing-Machine_Learning_Blog。如果收藏star, 有问题可以随时与我交流, 谢谢大家！

链接：

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

直觉

这是一个典型的双指针问题。

输入：numbers = [2, 7, 11, 15], target = 9

输出：[1, 2]

解释：2 和 7 的和是 9。因此，index1 = 1, index2 = 2。我们返回 [1, 2]。

我们将左指针初始化在数组的起始位置，将右指针初始化在数组的末尾。while 循环条件是 while l < r。如果 nums[l] + nums[r] 的和小于目标值，我们将左指针右移，因为数组是按升序排序的。如果和大于目标值，我们将右指针左移以减少和。如果和等于目标值，我们返回索引 [l + 1, r + 1]。

我们应该在每次循环迭代中只移动左指针或右指针一次。否则，我们可能会错过正确的配对。例如，以下是一个错误的解决方案：

def twoSum(self, numbers, target):
    """
    :type numbers: List[int]
    :type target: int
    :rtype: List[int]
    """
    l = 0
    r = len(numbers) - 1
    while numbers[l] + numbers[r] > target:
        r -= 1
    while numbers[l] + numbers[r] < target:
        l += 1
    return [l+1, r+1]

这个解决方案是错误的。考虑 [1, 2, 3, 4, 4, 9] 和目标值 8。它将返回 [0, 5]，但它应该返回 [4, 5]。指针移动逻辑没有考虑同时检查两个指针。只调整一个指针可能会错过有效的配对，并且不处理边界条件。

方法

1. 设置两个指针：左指针在数组的起始位置（l = 0），右指针在数组的末尾（r = len(numbers) - 1）。
2. 在 l < r 时迭代：
   • 如果 numbers[l] + numbers[r] 的和小于目标值，将左指针右移（l += 1）。
   • 如果和大于目标值，将右指针左移（r -= 1）。
   • 如果和等于目标值，返回索引 [l + 1, r + 1]（基于 1 的索引）。

复杂度

• 时间复杂度：
  $$O(n)$$

  • 我们最多用两个指针遍历列表一次，时间复杂度是线性的。

• 空间复杂度：
  $$O(1)$$

  • 我们只使用了常量空间来存储指针和临时变量。

代码

class Solution(object):
    def twoSum(self, numbers, target):
        """
        :type numbers: List[int]
        :type target: int
        :rtype: List[int]
        """
        l = 0
        r = len(numbers) -1
        while l < r:
            if numbers[l] + numbers[r] < target:
                l+=1
            elif numbers[l] + numbers[r] > target:
                r-=1
            else:
                return[l+1, r+1]