溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
小編給大家分享一下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如何解決兩數之和問題”這篇文章的所有內容，感謝各位的閱讀！相信大家都有了一定的了解，希望分享的內容對大家有所幫助，如果還想學習更多知識，歡迎關注億速云行業資訊頻道！
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
