使用python實(shí)現(xiàn)兩數(shù)之和的畫解算法
題目描述
給定一個(gè)整數(shù)數(shù)組 nums
和一個(gè)整數(shù)目標(biāo)值 target
,請(qǐng)你在該數(shù)組中找出 和為目標(biāo)值 target
的那 兩個(gè) 整數(shù),并返回它們的數(shù)組下標(biāo)。
你可以假設(shè)每種輸入只會(huì)對(duì)應(yīng)一個(gè)答案。但是,數(shù)組中同一個(gè)元素在答案里不能重復(fù)出現(xiàn)。
你可以按任意順序返回答案。
示例 1:
輸入:nums = [2,7,11,15], target = 9
輸出:[0,1]
解釋:因?yàn)?nums[0] + nums[1] == 9 ,返回 [0, 1] 。
示例 2:
輸入:nums = [3,2,4], target = 6
輸出:[1,2]
示例 3:
輸入:nums = [3,3], target = 6
輸出:[0,1]
問題分析
1.暴力求解
兩層循環(huán),外層循環(huán)枚舉(或稱作選中一個(gè)標(biāo)桿),內(nèi)層循環(huán)從枚舉值之后開始遍歷,計(jì)算兩數(shù)的和是否等于target。
如果找到了兩個(gè)數(shù),那么返回這兩個(gè)數(shù)的下標(biāo)。
for(int i = 0; i < n - 1; ++i) { for(int j = i + 1; j < n; ++j ) { if nums[i] + nums[j] == target ... } }
暴力求解的算法時(shí)間復(fù)雜度為指數(shù)級(jí),也就是O(n^2)
分析暴力求解,我們發(fā)現(xiàn)存在重復(fù)搜索的情況,也就是對(duì)數(shù)組中的部分?jǐn)?shù)據(jù)搜索了多次。
那如何只對(duì)數(shù)組中的數(shù)據(jù)搜索1次(或常數(shù)級(jí)),然后求解呢?
我們知道,尋找一個(gè)數(shù)是否存在,最快的方法是通過hash表,在O(1)的時(shí)間復(fù)雜度之內(nèi)就可以判斷是否存在某個(gè)數(shù)。
2.哈希表求解
可對(duì)數(shù)組遍歷一次,然后將數(shù)據(jù)存入hash表,然后再遍歷一次數(shù)組
查找 target - currentdata
是否存在hash表中,如果存在,那么我們就尋找到了兩個(gè)數(shù)。
題目要求我們返回?cái)?shù)組的下標(biāo),那么我們的hash
表的key
是數(shù)組元素的值,value
是下標(biāo)。
- 這種方法在最壞的情況下,對(duì)數(shù)組遍歷了2次,也就是算法的時(shí)間復(fù)雜度是O(2n),去掉前導(dǎo)系數(shù)是O(n),雖然是相比暴力求解,算法的時(shí)間復(fù)雜度降低了,但是還有優(yōu)化的空間。
- 在遍歷數(shù)組并將數(shù)據(jù)放入hash表的同時(shí),我們也可以
find
(target - currentdata
)是否存在,如果存在那么就找到了滿足條件的兩個(gè)數(shù)。
find(9-4), 存在那返回這兩個(gè)數(shù)的下標(biāo),如果不存在,那么將 4 放入hash表。
find(9-6), 存在那返回這兩個(gè)數(shù)的下標(biāo),如果不存在,那么將 6 放入hash表。
在遍歷到元素5的時(shí)候,我們find(9-5),找到了這兩個(gè)數(shù)。
動(dòng)畫演示下這個(gè)過程
代碼實(shí)現(xiàn)
class Solution: def twoSum(self, nums: List[int], target: int) -> List[int]: hashtable = dict() for i, num in enumerate(nums): # ② map中查找是否有 target - curvalue的數(shù)據(jù) if target - num in hashtable: return [hashtable[target - num], i] # ① 數(shù)組中的每個(gè)數(shù)放入map中 hashtable[nums[i]] = i return []
以上就是使用python實(shí)現(xiàn)兩數(shù)之和的畫解算法的詳細(xì)內(nèi)容,更多關(guān)于python實(shí)現(xiàn)兩數(shù)之和的畫解算法的資料請(qǐng)關(guān)注本站其它相關(guān)文章!
版權(quán)聲明:本站文章來源標(biāo)注為YINGSOO的內(nèi)容版權(quán)均為本站所有,歡迎引用、轉(zhuǎn)載,請(qǐng)保持原文完整并注明來源及原文鏈接。禁止復(fù)制或仿造本網(wǎng)站,禁止在非www.sddonglingsh.com所屬的服務(wù)器上建立鏡像,否則將依法追究法律責(zé)任。本站部分內(nèi)容來源于網(wǎng)友推薦、互聯(lián)網(wǎng)收集整理而來,僅供學(xué)習(xí)參考,不代表本站立場,如有內(nèi)容涉嫌侵權(quán),請(qǐng)聯(lián)系alex-e#qq.com處理。