前言
眾所周知，算法題主要有兩大難點(diǎn)。
一是「實(shí)現(xiàn)」，即算法本身的難度。
二是「思路」，代表你能否想到使用這個(gè)算法來解決題目。
并且對(duì)于有一定刷題基礎(chǔ)的同學(xué)來說，力扣上大部分簡(jiǎn)單、中等題所涉及的算法都是非常常見的算法，即算法本身不存在難度，最大的難點(diǎn)在于「思路」貪心算法 背包問題 c，即如何想到適合本題的算法。
而解決「思路」問題，除了大量刷題積累經(jīng)驗(yàn)之外，還可以采用一定的「巧勁」，從時(shí)間復(fù)雜度這個(gè)角度入手篩選出合適的算法。本文的主要目的就是向大家介紹這種「巧勁」是如何在具體解題過程中發(fā)揮作用的，會(huì)分成三個(gè)部分帶大家介紹～（碼住收藏吧）
如何判斷時(shí)間復(fù)雜度
如何確定一道題合適的時(shí)間復(fù)雜度？最簡(jiǎn)單、快捷的方式就是通過觀察題目中的數(shù)據(jù)范圍來確定。
不過你可能馬上會(huì)反駁，力扣上并不是所有題目都有數(shù)據(jù)范圍，那又該如何確定？在沒有數(shù)據(jù)范圍的情況下也可以采用這種方式來思考，我們會(huì)在后續(xù)「練習(xí)」部分進(jìn)行詳細(xì)說明。
言歸正傳，如何通過數(shù)據(jù)范圍來確定合適的時(shí)間復(fù)雜度？
通常來說，在力扣上， 可以支持到 10*7 的時(shí)間復(fù)雜度；C++ 會(huì)稍微多一點(diǎn)，大概 10*7 - 10*8 之間。因此我們可以得到如下表所示的，數(shù)據(jù)范圍與算法大致時(shí)間復(fù)雜度的對(duì)應(yīng)表。
復(fù)雜度總結(jié)
此處有兩點(diǎn)需要注意：
1. 上圖僅列出了時(shí)間復(fù)雜度較為固定的常見算法，而類似于動(dòng)態(tài)規(guī)劃、貪心、暴力等時(shí)間復(fù)雜度百變多樣的算法并未列出。
2. O(logn) 的算法通常與 O(n) 的算法組合在一起，用于實(shí)現(xiàn) O(nlogn) 要求的題目。
練習(xí)
在講解具體題目之前，我們先明確下根據(jù)時(shí)間復(fù)雜度做題的具體流程：
1. 根據(jù)數(shù)據(jù)范圍選擇時(shí)間復(fù)雜度
2. 根據(jù)時(shí)間復(fù)雜度選擇對(duì)應(yīng)的常見算法集合
3. 思考題目特征，從集合中選出合適的算法
4. 根據(jù)選出的算法求解題目
例如下道題解
1248. 統(tǒng)計(jì)「優(yōu)美子數(shù)組」
題目描述：
給你一個(gè)整數(shù)數(shù)組 nums 和一個(gè)整數(shù) k。如果某個(gè)連續(xù)子數(shù)組中恰好有 k 個(gè)奇數(shù)數(shù)字，我們就認(rèn)為這個(gè)子數(shù)組是「優(yōu)美子數(shù)組」。請(qǐng)返回這個(gè)數(shù)組中 「優(yōu)美子數(shù)組」 的數(shù)目。
示例 1：
輸入：nums = [1,1,2,1,1], k = 3
輸出：2
解釋：包含 3 個(gè)奇數(shù)的子數(shù)組是 [1,1,2,1] 和 [1,2,1,1] 。示例 2：
輸入：nums = [2,4,6], k = 1
輸出：0
解釋：數(shù)列中不包含任何奇數(shù)，所以不存在優(yōu)美子數(shù)組。示例 3：
輸入：nums = [2,2,2,1,2,2,1,2,2,2], k = 2
輸出：16數(shù)據(jù)范圍：
1 <= nums.length <= 50000
1 <= nums[i] <= 10^5
1 <= k <= nums.length解決過程：
本題的數(shù)據(jù)范圍到達(dá)了 50000，因此我們將時(shí)間復(fù)雜度劃定在 O(n) 的范圍內(nèi)。
根據(jù)上述「常見算法 & 時(shí)間復(fù)雜度」圖，我們可以劃定本題的算法集合。由于此題明顯是數(shù)組上操作的問題，因此我們僅列出 O(n) 范圍內(nèi)關(guān)于數(shù)組的算法。
差分、前綴和、雙指針、桶排序、單調(diào)棧、單調(diào)隊(duì)列仔細(xì)觀察題干，可以發(fā)現(xiàn)本題有兩大關(guān)鍵特征：
1. 連續(xù)子數(shù)組
2. 子數(shù)組內(nèi)恰好有 k 個(gè)奇數(shù)數(shù)字
如果對(duì)「前綴和」算法有所掌握的話，憑借這兩大特征不難確定此題可以用「前綴和」求解。
令 sum[i] 表示數(shù)組第 0 個(gè)數(shù)到第 i 個(gè)數(shù)中奇數(shù)的個(gè)數(shù)，因此區(qū)間 [l, r] 符合題意，當(dāng)且僅當(dāng)下式成立：
sum[r]?sum[l?1]=k
由此我們可以令 mp[x] 表示有多少個(gè)節(jié)點(diǎn) i 滿足 sum[i] = x。然后從左向右枚舉，當(dāng)求得第 i 個(gè)點(diǎn)的 sum 值后，更新 mp[sum[i]] 數(shù)組，并計(jì)算有多少個(gè) l 滿足區(qū)間 [l, i] 符合題意。累加答案即可得到最終結(jié)果，具體實(shí)現(xiàn)可參看下述代碼。
C++ 代碼實(shí)現(xiàn)
class Solution {
vector mp;
public:
int numberOfSubarrays(vector& nums, int k) {
int sum = 0, ans = 0, n = nums.size();
mp.resize(n + 2, 0);
mp[0] = 1;
for(auto y:nums){
if(y % 2) sum++;
mp[sum]++;
if(sum-k >= 0) ans += mp[sum-k];
}
return ans;
}
}; 例題 2：
面試題 08.11. 硬幣
題目描述
硬幣。給定數(shù)量不限的硬幣，幣值為 25 分、10 分、5 分和 1 分，編寫代碼計(jì)算n分有幾種表示法。(結(jié)果可能會(huì)很大貪心算法 背包問題 c，你需要將結(jié)果模上)。
示例 1
輸入: n = 5
輸出：2
解釋: 有兩種方式可以湊成總金額:
5=5
5=1+1+1+1+1示例 2
輸入: n = 10
輸出：4
解釋: 有四種方式可以湊成總金額:
10=10
10=5+5
10=5+1+1+1+1+1
10=1+1+1+1+1+1+1+1+1+1數(shù)據(jù)范圍：
0 <= n (總金額) <= 1000000
解決過程
本題的數(shù)據(jù)范圍到達(dá)了 ，因此我們將時(shí)間復(fù)雜度劃定在 O(n) 的范圍內(nèi)。再仔細(xì)觀察一下「常見算法 & 時(shí)間復(fù)雜度」圖，可以發(fā)現(xiàn)由于只有 4 種面值的硬幣，因此 O(nm) 的背包也是可行的。
根據(jù)時(shí)間復(fù)雜度與「常見算法 & 時(shí)間復(fù)雜度」圖，我們可以劃定本題的算法集合。由于此題明顯與圖論、字符串等算法無關(guān)，因此我們僅列出 O(n) 、 O(nm) 范圍內(nèi)有一定可能性的算法。
差分、前綴和、雙指針、桶排序、單調(diào)棧、單調(diào)隊(duì)列、背包問題思考題目特征 => 從集合中選出合適算法
仔細(xì)觀察此題，可以發(fā)現(xiàn)如下幾個(gè)特征：
1. 四類硬幣
2. 每類硬幣數(shù)量不限
3. 求組成 n 的方案數(shù)
如果對(duì)「動(dòng)態(tài)規(guī)劃」有一定熟悉度的話，基本可以確定此題就是「動(dòng)態(tài)規(guī)劃問題」，因此本題具有很明顯的「子結(jié)構(gòu)」性質(zhì)。
然后再根據(jù)之前確定的時(shí)間復(fù)雜度 O(n) 、 O(nm) ，以及我們選出的算法，基本可以確定該動(dòng)態(tài)規(guī)劃問題的狀態(tài)，只有如下兩種：
1. f[i] 表示用四種硬幣組成 i 分的方案數(shù)，屬于典型線性 DP。
2. f[i][j] 表示用前 i 種硬幣組成 j 分的方案數(shù)，屬于背包問題。
再仔細(xì)思考兩種狀態(tài)的轉(zhuǎn)移方程，可以發(fā)現(xiàn)第二種采用背包思路的 DP 狀態(tài)更適合解決本題，且由于硬幣個(gè)數(shù)不限，因此是經(jīng)典的「完全背包」問題。所以我們可以直接列出如下的轉(zhuǎn)移方程（ coin[i] 表示第 i 類硬幣的面值）：
f[i][j] = f[i-1][j]
f[i][j] = f[i][j] + f[i][j-coin[i]]可以發(fā)現(xiàn)， f[i][j] 的數(shù)值主要由 f [i?1][j] 與 f[i][j?coin[j]] 得到，因此我們可以壓縮掉第一維，即采用滾動(dòng)數(shù)組的方法，得到如下方程：
f[j] = f[j] + f[j-coin[i]]由于「完全背包」是背包問題中的經(jīng)典模型，因此更具體的細(xì)節(jié)，大家可以參考下述代碼。
C++代碼實(shí)現(xiàn)
class Solution {
vector f;
int coin[4] = {25, 10, 5, 1}, mod = 1e9+7;
public:
int waysToChange(int n) {
f.resize(n + 2, 0);
f[0] = 1;
for(int i = 0; i < 4; i++)
for(int j = coin[i]; j <= n; j++)
f[j] = (f[j] + f[j-coin[i]]) % mod;
return f[n];
}
}; 總結(jié)
最后，我們來總結(jié)一下「數(shù)據(jù)范圍」=> 「最終算法」的總體過程，如下圖所示。
除此之外，還需注意，從「數(shù)據(jù)范圍」入手思考「最終算法」只是獲取題目思路的手段之一，并且在上述流程圖中，「根據(jù)題目特征，篩選算法」是最為關(guān)鍵的步驟，這不僅要求做題者具有「挖掘題目特征」的能力，更要求做題者對(duì)于「常見算法」要有一定的熟悉度。
也正是因?yàn)檫@個(gè)原因，「常見算法 & 時(shí)間復(fù)雜度」對(duì)應(yīng)圖是具有個(gè)人特征的。每個(gè)人由于掌握的算法不同，「常見算法 & 時(shí)間復(fù)雜度」圖也各不相同，因此希望大家能夠有意識(shí)地構(gòu)建屬于自己的「常見算法 & 時(shí)間復(fù)雜度」圖，并在刷題的過程中，不斷更新，不斷完善。力求能夠在遇到自己掌握范圍內(nèi)的算法題時(shí)，一舉擊破。如果還是沒有頭緒，不妨試下下面的方法：
大家在做算法題時(shí)需要循序漸進(jìn)，上來如果直接就做 hard 題有些耗時(shí)間，但并不是不能做，只是性價(jià)比很低，先做熟練較低難度的題目，熟練掌握所有算法之后相當(dāng)于掌握了各種工具，當(dāng)算法如臂使指時(shí)，做起 hard 題來就會(huì)得心應(yīng)手。
如果對(duì) DP、DFS、BFS，二分法很熟悉，我建議可以先從簡(jiǎn)單的數(shù)據(jù)結(jié)構(gòu)開始，從隊(duì)列、堆，二叉樹到更復(fù)雜的紅黑樹、線段樹，盡可能都可掌握。
這里推薦一本書 《圖解算法數(shù)據(jù)結(jié)構(gòu)》，這本書是由力扣平臺(tái)知名創(chuàng)作者「」傾心打造，面向算法零基礎(chǔ)學(xué)習(xí)者，以圖文并茂的方式講解算法基礎(chǔ)知識(shí)與求職熱門算法題。學(xué)完你將會(huì)掌握：
數(shù)據(jù)結(jié)構(gòu)與算法的核心知識(shí)點(diǎn)熟悉互聯(lián)網(wǎng)筆面試的主要算法題型
思考時(shí)間復(fù)雜度可以減少大量試錯(cuò)機(jī)會(huì)。如果你想出的算法在時(shí)間復(fù)雜度上無法滿足題目給出的數(shù)據(jù)規(guī)模，那就說明算法還是有問題，需要思考更好的算法。有的時(shí)候，會(huì)有些模糊，比如剛好不過，或者差一點(diǎn)，那說明可能需要進(jìn)行優(yōu)化或剪枝。
做出思考很久的題目的快感是很爽，但確也浪費(fèi)時(shí)間，我們的建議是平衡好兩者，思考一個(gè)小時(shí)后如果沒有結(jié)果就看解答。事實(shí)上很多時(shí)候超過一個(gè)小時(shí)以后還沒想出來最優(yōu)解，就很難在短時(shí)間內(nèi)想出來了。
總的來說，刷算法題有點(diǎn)像一個(gè)模擬經(jīng)營(yíng)游戲，要平衡好學(xué)習(xí)和做題的節(jié)奏，不能操之過急，也不能把節(jié)奏放的太慢。評(píng)論留言少 BUG ！點(diǎn)贊轉(zhuǎn)發(fā)不脫發(fā)！
BY /