LeetCode如何解決兩數(shù)之和問題

發(fā)布時(shí)間：2021-12-15 10:52:45 來源：億速云閱讀：123 作者：小新欄目：大數(shù)據(jù)

小編給大家分享一下LeetCode如何解決兩數(shù)之和問題，相信大部分人都還不怎么了解，因此分享這篇文章給大家參考一下，希望大家閱讀完這篇文章后大有收獲，下面讓我們一起去了解一下吧！

題目描述

給定一個(gè)已按照升序排列的有序數(shù)組，找到兩個(gè)數(shù)使得它們相加之和等于目標(biāo)數(shù)，并滿足兩個(gè)要求：1、按照先后順序輸出兩個(gè)數(shù)的下標(biāo)值，下標(biāo)值從1開始；2、假設(shè)每個(gè)輸入只對(duì)應(yīng)唯一的答案，不可以重復(fù)使用相同的元素。如輸入數(shù)組為[2,6,7,9]，目標(biāo)值為8，則返回[1,2]，[2,1]不為正確答案。

2
2

解題

思路一：哈希表

與LeetCode刷題DAY 8：兩數(shù)之和中的思路二一致，只不過輸出時(shí)要把下標(biāo)+1，不然下標(biāo)是從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

思路二：雙指針

因?yàn)閿?shù)組是按照升序排列的，因此可以設(shè)置兩個(gè)指針分別指向數(shù)組兩端，即最小和最大值。計(jì)算指針指向數(shù)字的和，如果大于target，大數(shù)字指針減1，如果小于target，小數(shù)字指針加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

思路三：二分法

二分查找是一種效率較高的查找方法，也叫折半查找。對(duì)于一個(gè)順序存儲(chǔ)且里面元素是有序排列的結(jié)構(gòu)，判斷中間位置的值是否與目標(biāo)值一致，如不一致則根據(jù)大小關(guān)系在中間值切割的前后兩個(gè)子表中，重復(fù)前述操作進(jìn)行查找。

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如何解決兩數(shù)之和問題”這篇文章的所有內(nèi)容，感謝各位的閱讀！相信大家都有了一定的了解，希望分享的內(nèi)容對(duì)大家有所幫助，如果還想學(xué)習(xí)更多知識(shí)，歡迎關(guān)注億速云行業(yè)資訊頻道！

向AI問一下細(xì)節(jié)

LeetCode如何解決兩數(shù)之和問題

猜你喜歡

最新資訊

相關(guān)推薦

相關(guān)標(biāo)簽