快捷導(dǎo)航

使用python實(shí)現(xiàn)兩數(shù)之和的畫解算法

更新時(shí)間：2021年08月31日 12:39:37 作者：不吃西紅柿丶

這篇文章主要介紹了使用python實(shí)現(xiàn)兩數(shù)之和的畫解算法，采用實(shí)例問題的描述來進(jìn)行問題分析，并給出用暴力求解和哈希表兩種方法解決方案，有需要的朋友可以參考下

題目描述

給定一個(gè)整數(shù)數(shù)組 nums 和一個(gè)整數(shù)目標(biāo)值 target，請你在該數(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è)過程

2021-06-06 222452.gif

代碼實(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ù)之和的畫解算法的資料請關(guān)注腳本之家其它相關(guān)文章！

您可能感興趣的文章: