（一）線性枚舉

學(xué)習(xí)線性枚舉前，我們先來看個例題：精準(zhǔn)空降鏈接

概念

? ? ? ?枚舉的概念就是把滿足題目條件的所有情況都列舉出來，然后一一判定，從而找到最優(yōu)解的過程。線性枚舉一般是發(fā)生在順序表上（注意這里的順序表不一定有序，只是代表內(nèi)存連續(xù)的意思），例如我們求一個數(shù)組中的最大值，可以通過遍歷數(shù)組，對每個數(shù)進行訪問和判定，從而找到最大值，這種就是最樸素的枚舉算法。

例題

分析

? ? ? ?這個題目，最樸素的思路就是枚舉遞增的四個下標(biāo)，然后判斷是否滿足題目中給定的條件，如果滿足則計數(shù)器 +1，最后返回計數(shù)器，這種思路是最容易想到的，也就是傳說中的暴力算法，由于枚舉的過程中是順序遍歷數(shù)組的，所以也叫 線性枚舉。
? ? ? ?容易得知，這種做法的算法時間復(fù)雜度是 O(n^4)，對于 n ≥ 50 的情況已經(jīng)不堪重負了。

優(yōu)化

? ? ? ?那么如何進行優(yōu)化呢？O(n^3) 的時間復(fù)雜度比較好想，確定中間兩個下標(biāo) (j, k)，然后分別確定左邊的 i 和 右邊的 l，利用乘法原理相乘，再累加就能得到答案了。這里我們來說說 O(n^2) 的算法。
? ? ? ?用一個 cnt?數(shù)組來記錄以 j?作為中間那個數(shù)的 1 3 2 的三元數(shù)對，其中 j 是中間那個最大的數(shù)的下標(biāo)：

? ? ?a[ j ] < a[ l ] 時， a[ l ] 扮演的是四元組的第四個數(shù)，那么就可以將 cnt[ j ] 累加到結(jié)果 ans 中，并且用 x 來記錄，到目前為止，比 a[ l ] 小的數(shù)的個數(shù)，那么這種情況下 x 自然要自增。
? ? a[ j ] > a[ l?] 時，a[ l ] 扮演的是三元組 1 3 2 的第三個數(shù)，而我們之前已經(jīng)統(tǒng)計出小于 a[ l ] 的數(shù)是 x 個，自然滿足 1 3 2 這樣的三元數(shù)對的數(shù)目就是 x，把它累加到 cnt[ j ] 上即可。

? ? 最后返回 ans 就是所有統(tǒng)計出來的 滿足 a[ i ] < a[ k ] < a[ j ] < a[ l ] 的四元組的個數(shù)了。代碼很簡潔，可以反復(fù)觀摩。

（二）二分枚舉

學(xué)習(xí)二分枚舉前，我們先來看個例題：精準(zhǔn)空降鏈接

概念

? ? ? ?二分枚舉和線性枚舉的區(qū)別就是：可以用折半的方法的對數(shù)據(jù)進行可行性判定，從而可以通過對數(shù)的時間復(fù)雜度，求解出問題的解。當(dāng)然，二分枚舉的要求是這個順序表必須是有序表（即必須滿足單調(diào)性，可以是單調(diào)遞增、單調(diào)遞減、單調(diào)不增、單調(diào)不降）。

? ? ? ?二分枚舉本身的邏輯比較簡單，但是一個題是否能夠用二分來解決，是需要通過不斷的訓(xùn)練和刷題鍛煉出來的。

例題

分析

? ? ? ?但凡遇到求最大的最小值，或者最小的最大值，都可以優(yōu)先想到用二分來枚舉答案，然后對答案進行可行性判定。這個題如果不用二分枚舉，我們可以從將 val 從?1 開始枚舉，直到 100000000，寫一個 check 函數(shù)，函數(shù)的功能就是返回一個布爾值，判定一個數(shù)組 nums 是否能夠分成 m 組，并且每組的元素和不大于 val，如下：

優(yōu)化

? ? ? ?如果這個 check 函數(shù)的作用能夠看懂，那么相比你應(yīng)該能夠想到 val 是滿足單調(diào)性的，也就是 val 越大， check 能夠通過的概率也就越大，所以我們的目的就是找到 val 的臨界值，如果用線性枚舉的方式，就是 for 循環(huán)枚舉枚舉 val 的值，然后 check 判斷可行性，很明顯這樣的算法時間復(fù)雜度很高，但是如果用 二分的方式去枚舉 val 的值，然后用 check 來判斷可行性，就把枚舉的時間復(fù)雜度大大降低了。
? ? ? ?l 和 r 表示 val 的左右邊界， ans 代表最終我們找到的那個最小的滿足條件的答案。那么尋找 l 和 r 的中點，進行 check 判定，如果滿足條件，則 mid 必然是一個可行解，存儲到 ans 中，然后再去判斷 [l, mid) 這個左閉右開區(qū)間中，是否有更小的滿足條件的值，于是右區(qū)間就變成了 mid - 1；否則，就必須要去 (mid,?r] 這個區(qū)間中找了。

? ? ? ?最終， ans 存儲下來的一定是我們的最優(yōu)解。

（三）雙指針

學(xué)習(xí)雙指針前，讓我們先來看個例題：精準(zhǔn)空降鏈接

概念

? ? ? ?雙指針一般也是在有序數(shù)組上進行枚舉的算法，對于一個有序表，先定義左右兩個指針，分別從有序表的兩端往中間靠攏，從而不斷找到最優(yōu)解、或者累加可行解的過程。

例題

分析

? ? ? ?學(xué)過線性枚舉以后，最直白的想法就是直接枚舉兩個下標(biāo)，然后對兩者值的和進行如下判定，滿足條件的進行計數(shù)，但是這種做法，時間復(fù)雜度 O(n^2)：

優(yōu)化

? ? ? ? 我們可以單獨實現(xiàn)一個 countLessThan 函數(shù)，來計算數(shù)組中小于等于 value 的數(shù)對的個數(shù)，然后調(diào)用兩次，相減即可（類似 部分和 的算法思想）。

? ? ? ? 而對于一個有序數(shù)組，求多少個數(shù)對滿足它們的和小于等于 value，就可以用雙指針來求解，初始化兩個指針 l = 0，r = n-1，如果 nums[l] + nums[r] 小于等于 value，則以 l 開頭的數(shù)對數(shù)目就是 r - l，累加到 ans 中，左指針 + 1；否則，右指針 -1；

? ? ? ?最后返回 ans，就是我們要求的解了。

（四）哈希表

學(xué)習(xí)哈希表，那么我們先來看個例題：精準(zhǔn)空降鏈接

概念

? ? ? ?哈希表作為一個經(jīng)典的數(shù)據(jù)結(jié)構(gòu)，是利用數(shù)組來進行實現(xiàn)的，當(dāng)然底層原理比較長，這里就先不做介紹了，后續(xù)可以專門開個章節(jié)來講。python 中的字典，底層實現(xiàn)就是哈希表，所以能夠做到快速的增刪改查。

例題

分析

? ? ? ?順序枚舉每一個數(shù)，每次枚舉一個數(shù)，就把它插入到哈希表 index 中，而下次查找的時候，則通過 target - nums[i] 去查，如果能夠查到，則必然存在兩個數(shù)相加等于 target。
? ? ? ?但是，光找到這個數(shù)是不夠的，還需要知道兩者的下標(biāo)，所以插入的時候，值作為下標(biāo)即可。也就是插入的鍵值對是 （nums[i], i），也就是建立了一個反差表。

? ? ? ?好啦，如果你覺得這些內(nèi)容對你有用，麻煩給我的文章或者視頻點上一個贊吧，這樣也會更好的激勵我創(chuàng)作出更多優(yōu)質(zhì)的內(nèi)容，予人玫瑰??，手留余香，謝謝~~