每日一道leetcode（python）167. 两数之和 II - 输入有序数组

每日一道leetcode（python）167. 两数之和 II - 输入有序数组

2021-08-17

给定一个已按照 升序排列
的整数数组 numbers ，请你从数组中找出两个数满足相加之和等于目标数 target 。
函数应该以长度为 2 的整数数组的形式返回这两个数的下标值。numbers 的下标 从 1 开始计数 ，所以答案数组应当满足 1 <= answer[0] < answer[1] <= numbers.length 。
你可以假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素。
示例 1：
输入：numbers = [2,7,11,15], target = 9
输出：[1,2]
解释：2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。
示例 2：
输入：numbers = [2,3,4], target = 6
输出：[1,3]
示例 3：
输入：numbers = [-1,0], target = -1
输出：[1,2]
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/two-sum-ii-input-array-is-sorted
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

暴力求解
会超时

class Solution:
def twoSum(self, numbers: List[int], target: int) -> List[int]:
res = []
n = len(numbers)
for i in range(n - 1):
for j in range(i + 1,n):
if numbers[i] + numbers[j] == target:
res.append(i + 1)
res.append(j + 1)
return res

思路
由于给定的是有序数组，所以用双指针实现，时间复杂度为O(n)，空间复杂度为O(1)。

• 前后两个指针，当两指针指向位置的数字之和大于target时，后指针往前走；
• 当两指针指向位置的数字之和小于target时，前指针往后走；
• 循环终止条件时front<target(因为题目要求不可以重复使用相同的元素)。

class Solution:
def twoSum(self, numbers: List[int], target: int) -> List[int]:
left, right = 0, len(numbers)-1
# 初始化左右指针位置
while left < right:
s = numbers[left] + numbers[right]
# 求和
if s == target:
# 如果找到了这两个数
return [left+1, right+1]
# 题目中描述的下标索引是从1开始的
elif s > target:
# 如果两数之和大于目标值
right -= 1
# 右指针左移
else:
# 否则
left += 1
# 左指针右移
return []

最后

以上就是鲜艳花生为你收集整理的每日一道leetcode（python）167. 两数之和 II - 输入有序数组的全部内容，希望文章能够帮你解决每日一道leetcode（python）167. 两数之和 II - 输入有序数组所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。