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

本文主要是介绍【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 = 0r = len(numbers) - 1while numbers[l] + numbers[r] > target:r -= 1while numbers[l] + numbers[r] < target:l += 1return [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 = 0r = len(numbers) -1while l < r:if numbers[l] + numbers[r] < target:l+=1elif numbers[l] + numbers[r] > target:r-=1else:return[l+1, r+1]

这篇关于【LeetCode最详尽解答】167-两数之和 II-输入有序数组 Two-Sum-II-Input-Array-Is-Sorted的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---