【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]
。指针移动逻辑没有考虑同时检查两个指针。只调整一个指针可能会错过有效的配对,并且不处理边界条件。
方法
- 设置两个指针:左指针在数组的起始位置(
l = 0
),右指针在数组的末尾(r = len(numbers) - 1
)。 - 在
l < r
时迭代:- 如果
numbers[l] + numbers[r]
的和小于目标值,将左指针右移(l += 1
)。 - 如果和大于目标值,将右指针左移(
r -= 1
)。 - 如果和等于目标值,返回索引
[l + 1, r + 1]
(基于 1 的索引)。
- 如果
复杂度
时间复杂度:
O
(
n
)
O(n)
O(n)
- 我们最多用两个指针遍历列表一次,时间复杂度是线性的。
空间复杂度:
O
(
1
)
O(1)
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]