本题可以用哈希、双指针、二分查找三个思路进行求解,同时应建立有序列表与二分法的思维反射。
1
题目描述
给定一个已按照升序排列的有序数组,找到两个数使得它们相加之和等于目标数,并满足两个要求:1、按照先后顺序输出两个数的下标值,下标值从1开始;2、假设每个输入只对应唯一的答案,不可以重复使用相同的元素。如输入数组为[2,6,7,9],目标值为8,则返回[1,2],[2,1]不为正确答案。
2 2
解题
思路一:哈希表
与LeetCode刷题DAY 8:两数之和中的思路二一致,只不过输出时要把下标+1,不然下标是从0开始。
class Solution:
def twoSum(self, numbers: List[int], target: int) -> List[int]:
h_map = {}
for i,item in enumerate(numbers):
if target-item in h_map:
return [h_map[target-item]+1,i+1]
h_map[item] = i
思路二:双指针
因为数组是按照升序排列的,因此可以设置两个指针分别指向数组两端,即最小和最大值。计算指针指向数字的和,如果大于target,大数字指针减1,如果小于target,小数字指针加1,如果正好相等则输出。
class Solution:
def twoSum(self, numbers: List[int], target: int) -> List[int]:
i=0
j=len(numbers)-1
while i<j :
if numbers[i]+numbers[j]==target:
return [i+1,j+1]
elif numbers[i]+numbers[j]<target:
i+=1
else:
j-=1
思路三:二分法
二分查找是一种效率较高的查找方法,也叫折半查找。对于一个顺序存储且里面元素是有序排列的结构,判断中间位置的值是否与目标值一致,如不一致则根据大小关系在中间值切割的前后两个子表中,重复前述操作进行查找。
class Solution:
def twoSum(self, numbers: List[int], target: int) -> List[int]:
for i in range(len(numbers)):
a=i+1
b=len(numbers)-1
while a<=b:
if numbers[(a+b)//2]+numbers[i]<target:
a = max((a+b)//2,a+1)
elif numbers[(a+b)//2]+numbers[i]>target:
b = min((a+b)//2,b-1)
else:
return [i+1,(a+b)//2+1]