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

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

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

想進大廠, 刷演算法是必不可少的, 歡迎和博主一起打卡刷力扣演算法, 博主同步更新了演算法視頻講解 和 其他文章/導圖講解, 更易于理解, 歡迎來看!

文章目錄

• 一.你還在用暴力法解 兩數之和 嗎? 力扣1詳細注解
• • 0.導圖整理
  • 1.暴力法
  • 2.兩遍哈希表
  • 3.一遍哈希表
  • 4.哈希表中的回圈和異議
  • 5.java和Python中哈希表的差別
  • 原始碼
  • • Python:
    • java:
• 二.兩數之和II有序陣列, 多個有序, 思路全變, 力扣167詳細注解
• • 0.導圖整理
  • 1.兩數之和中有序和無序的區別
  • 2.二分法和尋找插入位置的區別
  • 3.雙指標思想
  • 原始碼
  • • Python:
    • java:
• 三.三數之和 相比于 兩數之和 的難點, 力扣15詳細注解
• • 0.導圖整理
  • 1.對于不重復三元組的處理
  • 2.雙指標的思想
  • 3.元素為整型鏈表的陣列鏈表: ArrayList

一.你還在用暴力法解 兩數之和 嗎? 力扣1詳細注解

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

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");
    }
}

二.兩數之和II有序陣列, 多個有序, 思路全變, 力扣167詳細注解

題目鏈接: https://leetcode-cn.com/problems/two-sum-ii-input-array-is-sorted/

0.導圖整理

1.兩數之和中有序和無序的區別

之前寫了一篇關于無序陣列的兩數之和問題, 在無序陣列中尋找第二個數就沒有多少捷徑, 畢竟陣列無序, 很多經典的方法都用不上, 最后只能犧牲空間來換取時間, 利用哈希表將空間復雜度增加到了O(n), 從而降低了尋找第二個數的時間復雜度.

但是當陣列有序之后, 就能使用一些經典的演算法同時仍然保證空間復雜度為O(1), 不需要犧牲空間來換取時間, 比如下面馬上介紹的 二分法 和 雙指標 方法.

這里給我們提供了一種思維, 那我們是不是也可以將無序陣列先進行排序后, 再使用這些經典演算法呢? 當然可以這么做, 但對于兩數之和來說, 必要性不是太大. 因為最快的排序演算法也需要O(nlogn)的時間復雜度, 對于兩數之和確實提升也不是太大, 但是對于 三數之和/四數之和 還是挺實用的, 后續文章將很快講到.

2.二分法和尋找插入位置的區別

陣列有序了, 使用二分法尋找第二個數就可以將時間復雜度降到O(logn)了, 關于二分法, 之前的這篇文章已經講解的很清楚了, 這里就不再重復介紹了.

這里說說 二分法 和 尋找插入位置的不同, 也是兩篇文章中代碼不同的部分.

尋找插入位置 最終無論是否找到目標值, 回傳的位置結果都是相同的, 而且題中說明陣列中無重復元素, 保證了回傳位置的唯一性, 所以最終 left == right == mid, 回傳哪個都無所謂, 也并不需要特殊的將 等于目標值 這個情況單獨寫出來, 所以代碼只討論了兩種情況, 最終一個回傳值, 非常簡潔.

但是對于本題使用的二分法, 首先并沒有要求陣列無重復元素, 其次, 我們要的是具體的 等于目標值 的位置, 并不是尋找插入位置, 所以在找不到的情況下, 我們只能回傳 [-1, -1], 首先的回傳結果就有了兩種情況.

其次由于有重復元素的存在, 若直接使用之前的只討論兩種情況的二分法是會出錯的, 這里必須要討論三種情況, 且在相等的情況下直接回傳正確的結果, 在找不到的情況下回傳 [-1, -1].

本題另外的一個小的注意點是: 回傳的下標從1開始, 只要在原本的回傳結果上+1就可以了.

還有一個注意點是, 為了避免重復尋找,在尋找第二個數時,只在第一個數的右側尋找, 也就是left = i+1.

3.雙指標思想

雙指標在有序陣列中是非常重要的思想, 一定要掌握. 思想還是挺簡單的, 但是優化的效果是非常棒的, 比二分法更加優秀. 導圖中對思想的描述挺清楚了, 這里說下它的適用范圍吧.

最基本最首要的前提是 陣列一定要是有序的, 其次, 一定要涉及到幾個數之間的相互關系, 最常用的也就是幾個數相加等于某一定值的情況, 其他情況, 今后遇到了再細說. 常用于陣列和鏈表之中.

原始碼

Python:

# 二分法
class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        n = len(numbers)
        for i in range(n):
            left, right = i+1, n  # 采用左閉右開區間[left,right),left+1避免重復
            while left < right: # 右開所以不能有=,區間不存在
                mid = (right - left) // 2 + left # 防止溢位
                if numbers[mid] == target - numbers[i]: # 陣列中存在重復元素,必須判斷相等
                    return [i + 1, mid + 1] # 回傳的下標從1開始,都+1
                elif numbers[mid] > target - numbers[i]:
                    right = mid # 右開,真正右端點為mid-1
                else:
                    left = mid + 1 # 左閉,所以要+1
        
        return [-1, -1]

# 雙指標
class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        low, high = 0, len(numbers) - 1 # 確定兩個指標的位置
        while low < high: # 指標移動條件
            total = numbers[low] + numbers[high]
            if total == target:
                return [low + 1, high + 1] # // 回傳下標從1開始
            elif total < target:
                low += 1 # Python中沒有++ --的用法
            else:
                high -= 1


        return [-1, -1]

?

java:

// 二分法
class Solution {
    public int[] twoSum(int[] numbers, int target) {
        for (int i = 0; i < numbers.length; ++i) {
            int left = i+1, right = numbers.length; // 采用左閉右開區間[left,right),left+1避免重復
            while (left < right) {                // 右開所以不能有=,區間不存在
                int mid = (right - left) / 2 + left; // 防止溢位
                if (numbers[mid] == target - numbers[i]) { // 陣列中存在重復元素,必須判斷相等
                    return new int[]{i + 1, mid + 1};      // 回傳的下標從1開始,都+1
                } else if (numbers[mid] > target - numbers[i]) { //中點大于目標值,在左側
                    right = mid; // 右開,真正右端點為mid-1
                } else {
                    left = mid + 1; //左閉,所以要+1
                }
            }
        }
        return new int[]{-1, -1};
    }
}

// 雙指標
class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int low = 0, high = numbers.length - 1; // 確定兩個指標的位置
        while (low < high) { // 指標移動條件
            int sum = numbers[low] + numbers[high];
            if (sum == target) {
                return new int[]{low + 1, high + 1}; // 回傳下標從1開始
            } else if (sum < target) {
                ++low;
            } else {
                --high;
            }
        }
        return new int[]{-1, -1};
    }
}

?

三.三數之和 相比于 兩數之和 的難點, 力扣15詳細注解

題目鏈接: 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>()

這里補充說明下這個資料結構, 對于新手來說, 看著還是挺嚇人的呢! 我們從外到里依次來拆分這個結構. 首先最外面 ArrayList() 表明它的本質是一個陣列鏈表, 無論里面的元素是什么型別, 它最本質的結構都不會發生變化的. 再來看它里面所裝的結構是 List, 就是說這個陣列鏈表中的每一個元素都是一個鏈表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;
    }
}

?

四.四數之和 相比 三數之和 的大量優化, 力扣18詳細注解

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

0.導圖整理

1.思想同三數之和: 排序+雙指標

四數之和 本質上和 三數之和 是一樣的, 由于都有大量重復元素的存在, 都不能使用哈希表進行簡單的去重, 都需要先進行排序后才方便遍歷處理, 同時為了優化時間復雜度, 再加上雙指標方法的使用, 如果只是想簡單實作的話, 那么在 三數之和 上直接多加一重回圈, 修改一下細節, 本題就可以實作了, 但是上述代碼的不同點在于: 并非只是簡單的加了一重回圈而已, 而是進行了大量的優化處理.

2.在三數之和基礎上進行了大量的優化

因為 四數之和 相比較于 三數之和 來說, 情況更加復雜, 時間復雜度也更高, 而且這個時間復雜度通過演算法是很難降下來的, 我們只能通過對代碼進行優化, 直接減少大量不必要的遍歷情況, 從而來縮短代碼的運行時間.

對于代碼的優化主要分為兩大塊: 一部分是為了避免出現重復的四元組, 在遍歷上面的優化, 這部分內容和 三數之和 中是相似的處理, 只不過更加復雜.

首先是對前兩重回圈進行的去重操作, 當 i 或者 j 的值與前面的值相等時忽略, 之后又對 雙指標 進行了去重操作, 這里有個重要的注意點: 一定注意代碼中是 先進行了指標的移動還是先進行了去重的比較, 對于不同的順序, 比較的元素是完全不同的. 如果先進行了指標的移動, 對于左指標來說, 需要比較的元素就是 當前元素和前面的一個元素, 如果是先進行去重的比較, 那比較的元素就是 當前元素和后面的一個元素, 再進行指標的移動. 對于右指標的情況正好是完全相反的.

第二部分就是在回圈遍歷中先通過計算特定的四個數之和, 以此來判斷接下來的回圈操作情況.

比如 在確定第一個數 nums[i] 之后, 如果nums[i]+nums[i+1]+nums[i+2]+nums[i+3]>target, 也就是此時的最小的4個數之和都大于target, 說明此時剩下的三個數無論取什么值, 四數之和一定大于 target, 因此直接退出第一重回圈就可以了, 使用 break 關鍵字.

在確定第一個數 nums[i] 之后,如果nums[i]+nums[n?3]+nums[n?2]+nums[n?1]<target, 也就是此時的最大的4個數之和都小于target, 說明此時剩下的三個數無論取什么值, 四數之和一定小于 target,因此第一重回圈直接進入下一輪, 列舉nums[i+1], 使用 continue 關鍵字.

對于第二層回圈也是同樣的判斷方法, 通過這兩層回圈的判斷優化, 能直接刪去大量的不滿足情況, 減少代碼運行的時間. 這也能給我們帶來啟發, 在演算法層面不能進行優化的時候, 可以選擇對代碼的細節進行優化, 同樣可以起到節省時間的效果.

原始碼

Python:

class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        quadruplets = list() # 定義一個回傳值
        if not nums or len(nums) < 4:
            return quadruplets
        
        nums.sort()
        length = len(nums)
        # 定義4個指標i,j,left,right  i從0開始遍歷,j從i+1開始遍歷,留下left和right作為雙指標
        for i in range(length - 3):
            if i > 0 and nums[i] == nums[i - 1]: # 當i的值與前面的值相等時忽略
                continue
            # 獲取當前最小值,如果最小值比目標值大,說明后面越來越大的值根本沒戲
            if nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target:
                break # 這里使用的break,直接退出此次回圈,因為后面的數只會更大
            # 獲取當前最大值,如果最大值比目標值小,說明后面越來越小的值根本沒戲,忽略
            if nums[i] + nums[length - 3] + nums[length - 2] + nums[length - 1] < target:
                continue # 這里使用continue,繼續下一次回圈,因為下一次回圈有更大的數
            # 第二層回圈j,初始值指向i+1
            for j in range(i + 1, length - 2):
                if j > i + 1 and nums[j] == nums[j - 1]: # 當j的值與前面的值相等時忽略
                    continue
                if nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target:
                    break
                if nums[i] + nums[j] + nums[length - 2] + nums[length - 1] < target:
                    continue
                left, right = j + 1, length - 1
                # 雙指標遍歷,如果等于目標值,left++并去重,right--并去重,當當前和大于目標值時right--,當當前和小于目標值時left++
                while left < right:
                    total = nums[i] + nums[j] + nums[left] + nums[right]
                    if total == target:
                        quadruplets.append([nums[i], nums[j], nums[left], nums[right]])
                        left += 1 # left先+1之后,和它前面的left-1進行比較,若后+1,則和它后面的left+1進行比較
                        while left < right and nums[left] == nums[left - 1]:
                            left += 1
                        right -= 1
                        while left < right and nums[right] == nums[right + 1]:
                            right -= 1   
                    elif total < target:
                        left += 1
                    else:
                        right -= 1
        
        return quadruplets

java:

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> quadruplets = new ArrayList<List<Integer>>(); // 定義一個回傳值
        if (nums == null || nums.length < 4) {
            return quadruplets;
        }
        Arrays.sort(nums);
        int length = nums.length;
        // 定義4個指標i,j,left,right  i從0開始遍歷,j從i+1開始遍歷,留下left和right作為雙指標
        for (int i = 0; i < length - 3; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) { // 當i的值與前面的值相等時忽略
                continue;
            }
            // 獲取當前最小值,如果最小值比目標值大,說明后面越來越大的值根本沒戲
            if (nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) {
                break; // 這里使用的break,直接退出此次回圈,因為后面的數只會更大
            }
            // 獲取當前最大值,如果最大值比目標值小,說明后面越來越小的值根本沒戲,忽略
            if (nums[i] + nums[length - 3] + nums[length - 2] + nums[length - 1] < target) {
                continue; // 這里使用continue,繼續下一次回圈,因為下一次回圈有更大的數
            }
            // 第二層回圈j,初始值指向i+1
            for (int j = i + 1; j < length - 2; j++) {
                if (j > i + 1 && nums[j] == nums[j - 1]) { // 當j的值與前面的值相等時忽略
                    continue;
                }
                if (nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target) {
                    break;
                }
                if (nums[i] + nums[j] + nums[length - 2] + nums[length - 1] < target) {
                    continue;
                }
                int left = j + 1, right = length - 1;
                // 雙指標遍歷,如果等于目標值,left++并去重,right--并去重,當當前和大于目標值時right--,當當前和小于目標值時left++
                while (left < right) {
                    int sum = nums[i] + nums[j] + nums[left] + nums[right];
                    if (sum == target) {
                        quadruplets.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));
                        left++; // left先+1之后,和它前面的left-1進行比較,若后+1,則和它后面的left+1進行比較
                        while (left < right && nums[left] == nums[left - 1]) {
                            left++;
                        }
                        right--;
                        while (left < right && nums[right] == nums[right + 1]) {
                            right--;
                        }
                    } else if (sum < target) {
                        left++;
                    } else {
                        right--;
                    }
                }
            }
        }
        return quadruplets;
    }
}

五.四陣列的四數之和II,詳解Counter類實作哈希表計數,力扣454

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

0.導圖整理

1.維數太高, 分治處理

此題乍一看似乎和 四數之和 差不多, 但是本質上卻有著很大的區別, 首先無論是 三數之和 還是 四數之和, 它們都是在一個陣列上的操作, 本質上都是一維的, 同時它們都要求找到 不重復 的元組, 這就限制了我們不能簡單的使用哈希表進行去重操作, 最終只能將陣列排序后使用雙指標的方法.

但是本題是 四個獨立的陣列, 相當于是 四個維度, 想在四個維度上使用雙指標的方法顯然是不現實的. 同時此題只要求我們找到所有4個元素的和為0的元組個數即可, 并沒有要求是不重復的元組, 這樣就簡單了很多, 也是可以使用哈希表的方法的.

此題在使用哈希表的時候, 會遇到如下的三種情況:

1.HashMap存一個陣列,如A，然后計算三個陣列之和,如BCD，時間復雜度為：O(n)+O(n^3),得到O(n^3).

2.HashMap存三個陣列之和,如ABC，然后計算一個陣列,如D，時間復雜度為：O(n^3)+O(n),得到O(n^3).

3.HashMap存兩個陣列之和,如AB，然后計算兩個陣列之和,如CD，時間復雜度為：O(n^2)+O(n^2),得到O(n^2).

根據時間復雜度來看, 我們肯定選擇第三種情況.

確定了使用的方法(哈希表)以及分類的方法(兩兩分組), 接下來就是代碼的書寫了. 此題和 兩數之和 中使用的哈希表有著很大的區別, 在兩數之和中, 我們需要的是滿足條件的下標值, 所以在哈希表中的值存取的就是元組的下標值, 這點是很容易實作的. 但是在此題中我們需要的是所有滿足元素的個數, 所以哈希表中的值應存取出現的次數. 這相對于只存下標是有點難度的. 這就涉及到下文要講的幾個方法和類了.

2.Java中map的merge和getOrDefault方法

統計出現的次數, 在java中可以使用map類中的兩個方法進行實作.

一種是countAB.put(u + v, countAB.getOrDefault(u + v, 0) + 1), 這里比較重要的是getOrDefault(u + v, 0)方法, 它的含義是獲得鍵u + v對應的值, 也就是出現的次數, 如果當然哈希表中未出現, 則回傳默認值0. 通過后面的+1操作, 實作在現有次數上+1或者初始化次數為1, 然后將這個鍵值對放入到哈希表中.

另一種方法是countAB.merge(u+v, 1, (old,new_)->old+1), 這里使用了merge方法, 從名字就可以看出是 合并 的意思, 也就是將新出現的鍵值對和原來已有的鍵值對進行合并, 形成新的鍵值對. 中間的1表示如果原來沒有此鍵值對, 那么這個新鍵值對的值就是1(出現次數為1次). 最后的引數表示了新的值的相對于舊的值的變化情況, 這里就是+1的操作. 有一點要主要的是new_有個下劃線, 因為在java中new是創建物件的關鍵詞, 這里是為了區別開來. 這個函式的語法就是上文所示那樣, 具體的操作情況都可以根據實際來更改.

3.Python中的Counter類

在Python中哈希表是利用dict()字典來實作的, 但畢竟不是專為哈希表設計的類, 也沒有那么豐富的方法來使用. 但是Python中直接設計了能夠對哈希物件進行計數的類, 并且在功能上更加優秀, 下面我們重點介紹一下這個類.

3.1 簡介

1.一個 Counter 是一個 dict 的子類, 用于計數可哈希物件，它是一個集合, 元素像字典鍵(key)一樣存盤, 它們的計數存盤為值，計數可以是任何整數值, 包括0和負數.

2.通常字典方法都可用于 Counter 物件,除了有兩個方法作業方式與字典并不相同
fromkeys(iterable)這個類方法沒有在 Counter 中實作
update([iterable-or-mapping]是在原有的鍵值對上加上,而不是替換

sum(c.values())                 # total of all counts
c.clear()                       # reset all counts
list(c)                         # list unique elements
set(c)                          # convert to a set
dict(c)                         # convert to a regular dictionary
c.items()                       # convert to a list of (elem, cnt) pairs
Counter(dict(list_of_pairs))    # convert from a list of (elem, cnt) pairs
c.most_common()[:-n-1:-1]       # n least common elements
+c                              # remove zero and negative counts

3.2 初始化

元素從一個 iterable 被計數或從其他的 mapping (or counter)初始化

c = Counter()                           # a new, empty counter
c = Counter('gallahad')                 # a new counter from an iterable
c = Counter({'red': 4, 'blue': 2})      # a new counter from a mapping
c = Counter(cats=4, dogs=8)             # a new counter from keyword args

3.3 空的處理

Counter物件有一個字典介面,如果參考的鍵沒有任何記錄,就回傳一個0,而不是彈出一個KeyError

c = Counter(['eggs', 'ham'])
c['bacon']                              # count of a missing element is zero
0

3.4 洗掉元素

設定一個計數為0不會從計數器中移去一個元素，使用 del 來洗掉它

c['sausage'] = 0                        # counter entry with a zero count
del c['sausage']                        # del actually removes the entry

3.5 elements()方法

回傳一個迭代器, 其中每個元素將重復出現計數值所指定次，元素會按首次出現的順序回傳，如果一個元素的計數值小于1, elements()將會忽略它

c = Counter(a=4, b=2, c=0, d=-2)
sorted(c.elements())
['a', 'a', 'a', 'a', 'b', 'b']

3.6 most_common([n])方法

回傳一個串列, 其中包含 n 個最常見的元素及出現次數, 按常見程度由高到低排序， 如果 n 被省略或為 None, most_common()將回傳計數器中的所有元素，計數值相等的元素按首次出現的順序排序

Counter('abracadabra').most_common(3)
[('a', 5), ('b', 2), ('r', 2)]

3.7 subtract([iterable-or-mapping])方法

從 迭代物件 或 映射物件 減去元素，像dict.update()但是是減去, 而不是替換，輸入和輸出都可以是0或者負數

c = Counter(a=4, b=2, c=0, d=-2)
d = Counter(a=1, b=2, c=3, d=4)
c.subtract(d)
c
Counter({'a': 3, 'b': 0, 'c': -3, 'd': -6})

3.8 數學操作

提供了幾個數學操作, 可以結合 Counter 物件, 以生產multisets (計數器中大于0的元素)，
加和減, 結合計數器, 通過加上或者減去元素的相應計數，
交集和并集回傳相應計數的最小或最大值，
每種操作都可以接受帶符號的計數, 但是輸出會忽略掉結果為零或者小于零的計數

sum(c.values())                 # total of all counts
c.clear()                       # reset all counts
list(c)                         # list unique elements
set(c)                          # convert to a set
dict(c)                         # convert to a regular dictionary
c.items()                       # convert to a list of (elem, cnt) pairs
Counter(dict(list_of_pairs))    # convert from a list of (elem, cnt) pairs
c.most_common()[:-n-1:-1]       # n least common elements
+c                              # remove zero and negative counts

3.9 注意點

1.計數器主要是為了表達運行的正的計數而設計；但是, 小心不要預先排除負數或者其他型別

2.Counter 類是一個字典的子類,不限制鍵和值，值用于表示計數, 但你實際上可以存盤任何其他值

3.most_common()方法在值需要排序的時候用

4.原地操作比如 c[key] += 1, 值型別只需要支持加和減，所以分數,小數,和十進制都可以用, 負值也可以支持，這兩個方法update()和subtract()的輸入和輸出也一樣支持負數和0

5.Multiset多集合方法只為正值的使用情況設計，輸入可以是負數或者0, 但只輸出計數為正的值，沒有型別限制, 但值型別需要支持加, 減和比較操作

6.elements()方法要求正整數計數，忽略0和負數計數

4.總結

1.看到形如：A+B…+N=0的式子,要轉換為(A+…T)=-((T+1)…+N)再計算,這個T的分割點一般是一半,特殊情況下需要自行判斷，定T是解題的關鍵

2.dp一般不會超過二維, 這里都四維了, 維度太高, 需要分治

3.演算法中間使用了map的新方法merge和getOrDefault, 相比較于傳統的判斷寫法, 大大提高了效率

原始碼

Python:

class Solution:
    def fourSumCount(self, A: List[int], B: List[int], C: List[int], D: List[int]) -> int:
        # Counter類是dict()子類, 用于計數可哈希物件
        # 它是一個集合,元素像字典鍵(key)一樣存盤,它們的計數存盤為值
        countAB = collections.Counter(u + v for u in A for v in B)
        ans = 0
        for u in C:
            for v in D:
                if -u - v in countAB:
                    ans += countAB[-u - v]
        return ans

java:

class Solution {
    public int fourSumCount(int[] A, int[] B, int[] C, int[] D) {
        Map<Integer, Integer> countAB = new HashMap<Integer, Integer>();
        for (int u : A) {
            for (int v : B) {
                // 存盤u+v的結果,不存在賦值為1,存在在原來基礎上+1
                // 另一種表達countAB.merge(u+v, 1, (old,new_)->old+1);
                countAB.put(u + v, countAB.getOrDefault(u + v, 0) + 1);
            }
        }
        int ans = 0;
        for (int u : C) {
            for (int v : D) {
                if (countAB.containsKey(-u - v)) {
                    ans += countAB.get(-u - v);
                }
            }
        }
        return ans;
    }
}

六.總結 n數之和 的各種情況 和 使用方法

前幾次的講解, 我們幾乎將陣列的各種求和都講解了一遍, 今天我們來對陣列的n數之和做個總結.

1.兩種常用的方法

1.1 哈希表

哈希表的方法首先用在了兩數之和(無序陣列)上, 哈希表的使用最主要的目的就是為了降低時間復雜度, 縮減尋找第二個元素使用的時間(將時間復雜度由O(n)降為O(1)), 其中無序陣列是哈希表使用的重要條件, 因為當陣列有序后, 我們完全可以直接使用 雙指標 的方法來降低時間復雜度, 它的使用比 哈希表 更加方便快捷, 空間復雜度也更低, 所以陣列有序之后, 我們應該首選 雙指標 的方法.

在使用哈希表的時候, 也有一個很重要的優化點, 就是 遍歷兩遍哈希表 和 遍歷一遍哈希表 的區別. 簡單來說就是, 如果我們先將第一個元素放入哈希表中, 然后再尋找第二個元素, 那么我們就需要 遍歷兩遍哈希表, 如果我們先尋找第二個元素, 之后再將元素放入到哈希表中, 那么就只需要 遍歷一遍哈希表. 說起來比較抽象, 大家可以看下面的兩種方法的代碼, 還不太清楚的話, 可以看上面 兩數之和 的文章.

上面是我們第一次使用哈希表的情況, 第二次使用哈希表就到了 四數之和II四陣列相加, 首先由于它具有四個獨立的陣列, 相當于四維空間, 所以我們很難在這么高的空間維度上直接使用 雙指標 的方法, 其次它并沒有要求 不重復元組 的情況, 這就給了我們使用 哈希表 的可能性, 因為不用擔心復雜的去重操作, 但是使用哈希表一般也是兩維的空間, 所以我們必須先進行降維操作, 也就是將四個陣列進行分組, 由三種結果的時間復雜度來判斷, 我們很容易就選擇了 兩兩分組 的情況.

之后對于哈希表的使用, 就是兩種不同情況的使用了. 如果需要直接回傳相應陣列的下標值, 那是很簡單的, 我們只需要將 下標值 當做 哈希表的值 即可.(兩數之和 中的使用)

如果需要進行計數, 那就有點麻煩了, 在java中我們可以使用map類的 getOrDefault 或者 merge 方法來實作, 在Python中我們可以直接使用 Counter類 實作, 具體程序可以看 四數之和II四陣列相加 的文章.

這是目前我們見到的使用哈希表的情況 和 哈希表的兩種使用方法, 今后遇到會再加以補充.

1.2 雙指標

對于n數之和, 除了哈希表的方法, 最常用的就是 雙指標 的方法了, 上文也提到了, 使用雙指標最重要的條件就是陣列是有序的, 當然這只是針對n數之和的題型, 對于其他題型, 并不需要要求陣列是有序, 例如我們馬上就會講到的 移除元素.

在n數之和中使用雙指標必要條件就是陣列是有序的, 這就需要我們根據實際情況來判斷 陣列是否需要進行排序. 比如在 兩數之和 中, 就算使用暴力法也才 O ( n 2 ) O(n^2) O(n2), 但進行排序最快也需要 O ( n l o n g ) O(nlong) O(nlong)的時間復雜度, 所以對于兩數之和來說, 是真的沒必要.

但是對于 三數之和 和 四數之和 就很有必要了, 因為它們時間復雜度實在太高了, 最關鍵的是它們元組的重復情況也比較多, 想利用哈希表進行去重是非常困難的, 最終只能選擇將陣列排序后使用 雙指標 的方法.

2. n數之和方法總結

對于兩數之和, 看它是否是有序的, 如果是無序的就使用 哈希表 的方法, 如果是有序的, 就可以使用 雙指標 的方法.

對于一個陣列上的三數之和/四數之和等, 無論陣列是否有序, 都排序后使用 雙指標 的方法.

對于多個陣列之和的情況, 首先對它們進行分組來實作降維操作, 一般來說都是分為兩個相等的小組, 之后再使用 哈希表 的方法.

情況比較多, 大家要根據具體情況判斷具體哪個方法更好, 時間/空間復雜度更低, 選擇最優秀的演算法.

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

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

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

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

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