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

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

關于本專欄所有題目的目錄鏈接, 刷演算法題目的順序/注意點/技巧, 以及思維導圖源檔案問題請點擊此鏈接. 歡迎和博主一起打卡刷力扣演算法, 博主同步更新了演算法視頻講解 和 其他文章/導圖講解, 更易于理解, 歡迎來看!

目錄

0.導圖整理

1.對于不重復三元組的處理

2.雙指標的思想

3.元素為整型鏈表的陣列鏈表: ArrayList>()

原始碼

題目鏈接: https://leetcode-cn.com/problems/3sum/

0.導圖整理

1.對于不重復三元組的處理

本題最大的難點在于題目要求的 不重復的三元組, 三數之和 不像 兩數之和 那樣簡單, 它的可重復情況是非常多的, 無法像 兩數之和 那樣, 只要將第一個元素放入哈希表中, 就可以輕松解決元素重復的問題了.

對于三數之和, 即使使用哈希表去重, 它的操作也是比較困難的. 所以我們不能簡單地使用三重回圈列舉所有的三元組, 然后使用哈希表進行去重操作, 這樣的作業量比較大.

因此我們必須換一種方法來解決此題, 從源頭上解決元素重復的問題. 如果給定的陣列是有序的, 那么其中可重復的情況就是完全可以控制的了, 處理起來也是很簡單的. 所以我們首先將陣列中的元素從小到大進行排序, 隨后使用普通的三重回圈就可以滿足上面的要求.

我們會發現其中重復的元組都是相鄰的元組, 只需要保證在每一重回圈時, 相鄰兩次列舉的元素不是相同的元素, 這樣就可以避免元組重復的情況了. 也就是導圖中每層回圈時的 if判斷陳述句.

2.雙指標的思想

使用普通的三層回圈確實也能解決問題, 但是O(n^3)的時間復雜度也確實太高了, 這時我們想到了在 有序陣列的兩數之和 中使用的雙指標的方式(雙指標在此文已說明清楚, 這里就不重復講解了), 雖然現在是三數之和, 但當我們正常遍歷了第一層回圈之后, 剩下的兩個數不就形成了 有序陣列的兩數之和 了嗎? 所以我們只要 保持第二重回圈不變, 而將第三重回圈變成一個從陣列最右端開始向左移動的指標, 同時加上上述討論的避免重復的條件, 最終代碼就完成了.

時間復雜度也從O(n^3)降到了O(n^2), 至于空間復雜度, 有兩種情況: 如果允許我們改變原來的陣列, 那么只需要排序演算法額外的空間復雜度O(logN), 如果不允許的話, 那就要使用了一個額外的陣列存盤了nums的副本并進行排序,空間復雜度為 O(N).

3.元素為整型鏈表的陣列鏈表: ArrayList<List<Integer>>()

這里補充說明下這個資料結構, 對于新手來說, 看著還是挺嚇人的呢! 我們從外到里依次來拆分這個結構. 首先最外面 ArrayList() 表明它的本質是一個陣列鏈表, 無論里面的元素是什么型別, 它最本質的結構都不會發生變化的. 再來看它里面所裝的結構是 List<Integer>, 就是說這個陣列鏈表中的每一個元素都是一個鏈表List, 長度可以是任意的長度, 但是這個鏈表List中的元素的型別必須是整型Integer. 這里的<>用到了java中的 泛型 的概念, 簡單來說就是一個寫一個通用的模板, 里面所包含元素的型別可以是任意的, 具體使用時對其指定具體的型別即可. 對于較復雜的資料型別, 一般都是采用這種由外到內的分析方法.

對應本題來說下具體的應用: ans.add(Arrays.asList(nums[first],nums[second],nums[third])), 首先ans這個陣列鏈表使用.add函式添加了一個鏈表, 而這個鏈表是通過 3個整型資料 由Arrays.asList()這個方法轉換成的鏈表, 這樣就成功添加了一個鏈表. 之后每次回圈, 只要有滿足條件的三元組都會添加一個鏈表, 最終所有滿足條件的三元組鏈表形成了最終結果的陣列鏈表ans.

對于java和C++這種強型別的語言, 使用時要明確指明所用到的資料型別, 但對于Python這種弱型別的語言來說, 用起來就非常簡單了, 你只需要創建了鏈表list(), 不需要指明任何型別, 使用時直接添加某種特定型別的資料即可. 而且每次添加的資料會自動保存為一個鏈表的形式添加到鏈表中, 不需要顯式地自己將其轉化為鏈表, 用起來還是很簡單的.

原始碼

Python:

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]: # 元素為整型鏈表的陣列鏈表
        n = len(nums)
        nums.sort()   # 將陣列進行排序
        ans = list()
        
        # 列舉 a
        for first in range(n):
            # 需要和上一次列舉的數不相同
            if first > 0 and nums[first] == nums[first - 1]:
                continue
            # c 對應的指標初始指向陣列的最右端
            third = n - 1
            target = -nums[first]
            # 列舉 b
            for second in range(first + 1, n):
                # 需要和上一次列舉的數不相同
                if second > first + 1 and nums[second] == nums[second - 1]:
                    continue
                # 需要保證 b 的指標在 c 的指標的左側
                while second < third and nums[second] + nums[third] > target:
                    third -= 1
                if second == third: # 如果指標重合,后續也不會滿足條件,可以退出回圈
                    break
                if nums[second] + nums[third] == target:
                    ans.append([nums[first], nums[second], nums[third]])
        
        return ans

java:

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        int n = nums.length;
        Arrays.sort(nums); //將陣列進行排序
        List<List<Integer>> ans = new ArrayList<List<Integer>>(); //元素為整型鏈表的陣列鏈表
        // 列舉 a
        for (int first = 0; first < n; ++first) {
            // 需要和上一次列舉的數不相同
            if (first > 0 && nums[first] == nums[first - 1]) {
                continue;
            }
            // c 對應的指標初始指向陣列的最右端
            int third = n - 1;
            int target = -nums[first];
            // 列舉 b
            for (int second = first + 1; second < n; ++second) {
                // 需要和上一次列舉的數不相同
                if (second > first + 1 && nums[second] == nums[second - 1]) {
                    continue;
                }
                // 需要保證 b 的指標在 c 的指標的左側
                while (second < third && nums[second] + nums[third] > target) {
                    --third;
                }
                if (second == third) { // 如果指標重合,后續也不會滿足條件,可以退出回圈
                    break;
                }
                if (nums[second] + nums[third] == target) {
                    ans.add(Arrays.asList(nums[first],nums[second],nums[third]));
                }
            }
        }
        return ans;
    }
}

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

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

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

力扣演算法刷題 根據思維導圖整理筆記快速記憶演算法重點內容(歡迎和博主一起打卡刷題哦)

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

最值得收藏的 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的性能情況和常見后綴的含義 思維導圖整理