此專欄文章是對力扣上演算法題目各種方法的總結和歸納, 整理出最重要的思路和知識重點并以思維導圖形式呈現, 當然也會加上我對導圖的詳解.

目的是為了更方便快捷的記憶和回憶演算法重點(不用每次都重復看題解), 畢竟演算法不是做了一遍就能完全記住的. 所以本文適合已經知道解題思路和方法, 想進一步加強理解和記憶的朋友, 并不適合第一次接觸此題的朋友(可以根據題號先去力扣看看官方題解, 然后再看本文內容).

關于本專欄所有題目的目錄鏈接, 刷演算法題目的順序/注意點/技巧, 以及思維導圖源檔案問題請點擊此鏈接. 導圖中原始碼在文章最后.

博主在公眾號 [一起學計算機]每日首發力扣演算法, 歡迎關注公眾號每日和博主一起刷題!

博主在 B站 同步更新了 演算法視頻講解 和 其他文章/導圖講解, 更易于理解, 歡迎來看!

目錄

0.導圖整理

1.暴力法

2.兩遍哈希表

3.一遍哈希表

4.哈希表中的回圈和異議

5.java和Python中哈希表的差別

原始碼

0.導圖整理

1.暴力法

暴力法的思想很簡單, 就是兩層回圈: 一層用來遍歷所有元素, 另一層用來尋找目標數.

但此題中的注意點是題目中的: 假設每種輸入只會對應一個答案. 但是, 陣列中同一個元素不能使用兩遍.

每種輸入只對應一個輸出 也就是要求我們找到滿足的元素直接回傳就可以了, 并不需要再去找其他滿足的元素, 這也為下面使用哈希表的方法提供了前提, 因為如果需要找到所有滿足的元素, 那么哈希表的結構就不能滿足要求了.

陣列中同一個元素不能使用兩遍 這個要求就是代碼中標注重點的部分 j = i + 1; 的含義. 當遍歷整個陣列尋找 target - x 時, 需要注意到每一個位于 x 之前的元素都已經和 x 匹配過, 因此不需要再進行匹配. 而每一個元素不能被使用兩次, x本身也不需要進行匹配, 所以只需要在 x 后面的元素中尋找 target - x, 也就是從i+1開始遍歷.

2.兩遍哈希表

暴力法使用了兩層回圈, 時間復雜度達到了O(n^2), 而使用哈希表就可以將尋找目標數的操作降為O(1), 直接降了一個量級, 具體程序如下:

使用了兩次迭代，在第一次迭代中, 將每個元素的值和它的索引添加到表中，然后, 在第二次迭代中, 檢查每個元素所對應的目標元素（target?nums[i]）是否存在于表中，注意, 該目標元素不能是 nums[i]本身！也就是 map.get(complement) != i 的含義.

3.一遍哈希表

對于上面方法還有一點優化, 就是將兩次迭代合并到一次中完成, 先進行匹配, 再插入到哈希表中!

首先創建一個哈希表, 對于每一個 x, 首先查詢哈希表中是否存在 target - x, 如果存在直接回傳結果就可以了. 之后將 x 插入到哈希表中, 即可保證不會讓 x 和自己匹配, 因為在匹配時, x還未插入到哈希表中.

這種優化對于時間復雜度沒有太大影響, 但是代碼看起來更簡潔了.

4.哈希表中的回圈和異議

對于使用哈希表的演算法, 有人提出了異議, HashMap的containsKey里面還有一個回圈, 也就還是O(n^2), map還增加了空間復雜度和開銷, 綜合來看還是暴力法最為有效, 但是這個觀點也有點問題: 這個containsKey里的回圈, 只有沖突了才會進入, 同時如果沖突頻繁, 會改用getTreeNode方法去獲取值, getTreeNode是從一棵紅黑樹中獲取值, 時間復雜度頂多O(logN), 綜合來看, 還是降低了時間復雜度. 對于紅黑樹感興趣的朋友, 可以看博主的這篇思維導圖.

5.java和Python中哈希表的差別

從上述代碼可以看出, 兩者對于哈希表的實作還是有很大的差別的.

首先java中的哈希表是用Map類實作的, 判斷是否包含一個元素用的是 map.containsKey(Key) 函式, 獲取 鍵 對應的 值 使用的是 map.get(Key) 函式, 插入到哈希表中使用的是 map.put(Key, Value)

但是在Python中直接使用它自帶的資料型別 字典dict 就實作了哈希表的操作, 并不需要新建類, 而且相應的操作也非常簡單, 幾乎不需要通過其他函式來實作. 判斷是否包含一個元素用的是 in, 獲取 鍵 對應的 值 使用的是 hashtable[Key] 函式, 插入到哈希表中使用的是 hashtable[Key] = Value

仔細對比會發現, Python語法是真的簡潔明了, 這也是博主喜歡Python的原因.

這里補充說明一下Python中的 enumerate(nums) 函式, 簡單來說就是對nums陣列中的所有數添加了下標, 它回傳的是 由下標和資料構成的二元元組, 在Python的for回圈中還是挺經常使用的函式.

原始碼

Python:

# 暴力法
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        n = len(nums)
        for i in range(n):
            for j in range(i + 1, n):
                if nums[i] + nums[j] == target:
                    return [i, j]

        return []


# 一遍哈希表
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        hashtable = dict()
        for i, num in enumerate(nums):
            if target - num in hashtable:
                return [hashtable[target - num], i]
            hashtable[nums[i]] = i
        return []

java:

// 暴力法
class Solution {
    public int[] twoSum(int[] nums, int target) {
         for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[j] == target - nums[i]) {
                    return new int[] { i, j };
                }
            }
        }
        throw new IllegalArgumentException("No two sum solution");
    }
}

//兩遍哈希表
class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            map.put(nums[i], i);
        }
        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];
            if (map.containsKey(complement) && map.get(complement) != i) {
                return new int[] { i, map.get(complement) };
            }
        }
        throw new IllegalArgumentException("No two sum solution");
    }
}

//一遍哈希表
class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];
            if (map.containsKey(complement)) {
                return new int[] { map.get(complement), i };
            }
            map.put(nums[i], i);
        }
        throw new IllegalArgumentException("No two sum solution");
    }
}

感覺作者寫的不錯的, 別忘了點贊關注加收藏哦(一鍵三連)!你的支持會帶給我極大的動力, 寫出更多優秀文章!

文章到這里就結束了, 感謝你的認真觀看, 為了感謝讀者們, 我把我一直以來整理的各種計算機相關/考研相關精品思維導圖/力扣演算法講解/面試資料/各種實用軟體工具分享給大家(并且會持續更新哦!), 希望能夠幫助到你們.

關注公眾號 [一起學計算機] 點擊 資源獲取 即可獲得所有資源, 包含的資源如下圖, 其中具體資源的相關講解和各種軟體的使用可以查看下面相應的文章.

我的更多精彩文章鏈接, 歡迎查看

各種電腦/軟體/生活/音樂/動漫/電影技巧匯總(你肯定能夠找到你需要的使用技巧)

力扣演算法刷題 根據思維導圖整理筆記快速記憶演算法重點內容(可在公眾號和博主一起打卡學習哦)

經典動漫全集目錄 精彩劇集

海賊王 動漫 全集目錄 分章節 精彩打斗劇集 思維導圖整理

火影忍者 動漫 全集目錄 分章節 精彩打斗劇集 思維導圖整理

死神 動漫 全集目錄 分章節 精彩打斗劇集 思維導圖整理

計算機專業知識 思維導圖整理

最值得收藏的 Python 全部知識點思維導圖整理, 附帶常用代碼/方法/庫/資料結構/常見錯誤/經典思想(持續更新中)

最值得收藏的 C++ 全部知識點思維導圖整理(清華大學鄭莉版), 東南大學軟體工程初試906科目

最值得收藏的 計算機網路 全部知識點思維導圖整理(王道考研), 附帶經典5層結構中英對照和框架簡介

最值得收藏的 演算法分析與設計 全部知識點思維導圖整理(北大慕課課程)

最值得收藏的 資料結構 全部知識點思維導圖整理(王道考研), 附帶經典題型整理

最值得收藏的 人工智能導論 全部知識點思維導圖整理(王萬良慕課課程)

最值得收藏的 數值分析 全部知識點思維導圖整理(東北大學慕課課程)

最值得收藏的 數字影像處理 全部知識點思維導圖整理(武漢大學慕課課程)

紅黑樹 一張導圖解決紅黑樹全部插入和洗掉問題 包含詳細操作原理 情況對比

各種常見排序演算法的時間/空間復雜度 是否穩定 演算法選取的情況 改進 思維導圖整理

人工智能課件 演算法分析課件 Python課件 數值分析課件 機器學習課件 影像處理課件

考研相關科目 知識點 思維導圖整理

考研經驗--東南大學軟體學院軟體工程(這些基礎課和專業課的各種坑和復習技巧你應該知道)

東南大學 軟體工程 906 資料結構 C++ 歷年真題 思維導圖整理

東南大學 軟體工程 復試3門科目歷年真題 思維導圖整理

最值得收藏的 考研高等數學 全部知識點思維導圖整理(張宇, 湯家鳳), 附做題技巧/易錯點/知識點整理

最值得收藏的 考研線性代數 全部知識點思維導圖整理(張宇, 湯家鳳), 附帶慣用思維/做題技巧/易錯點整理

高等數學 中值定理 一張思維導圖解決中值定理所有題型

考研思修 知識點 做題技巧 同類比較 重要會議 1800易錯題 思維導圖整理

考研近代史 知識點 做題技巧 同類比較 重要會議 1800易錯題 思維導圖整理

考研馬原 知識點 做題技巧 同類比較 重要會議 1800易錯題 思維導圖整理

考研數學課程筆記 考研英語課程筆記 考研英語單詞詞根詞綴記憶 考研政治課程筆記

Python相關技術 知識點 思維導圖整理

Numpy常見用法全部OneNote筆記 全部筆記思維導圖整理

Pandas常見用法全部OneNote筆記 全部筆記思維導圖整理

Matplotlib常見用法全部OneNote筆記 全部筆記思維導圖整理

PyTorch常見用法全部OneNote筆記 全部筆記思維導圖整理

Scikit-Learn常見用法全部OneNote筆記 全部筆記思維導圖整理

Java相關技術/ssm框架全部筆記

Spring springmvc Mybatis jsp

科技相關 小米手機

小米 紅米 歷代手機型號大全 發布時間 發布價格

常見手機品牌的各種系列劃分及其特點

歷代CPU和GPU的性能情況和常見后綴的含義 思維導圖整理