LeetCode如何解决两数之和问题
小编给大家分享一下LeetCode如何解决两数之和问题，相信大部分人都还不怎么了解，因此分享这篇文章给大家参考一下，希望大家阅读完这篇文章后大有收获，下面让我们一起去了解一下吧！
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]
以上是“LeetCode如何解决两数之和问题”这篇文章的所有内容，感谢各位的阅读！相信大家都有了一定的了解，希望分享的内容对大家有所帮助，如果还想学习更多知识，欢迎关注行业资讯频道！