很多同學(xué)剛接觸算法競(jìng)賽時(shí)第一反應(yīng)是去啃各種“高大上”的算法——圖論、動(dòng)態(tài)規(guī)劃、網(wǎng)絡(luò)流、字符串匹配。但真正讓我意識(shí)到“地基”重要性的是一次比賽中因?yàn)閿?shù)組開小導(dǎo)致半小時(shí)調(diào)不出錯(cuò)誤、最后發(fā)現(xiàn)是邊界問題的慘痛教訓(xùn)。數(shù)組這個(gè)最基礎(chǔ)、最不起眼的數(shù)據(jù)結(jié)構(gòu)恰恰是算法競(jìng)賽里幾乎所有解法的落腳點(diǎn)。你寫的每一份代碼本質(zhì)上都在操作數(shù)組狀態(tài)轉(zhuǎn)移存數(shù)組、鄰接表存數(shù)組、哈希沖突解決也依賴數(shù)組?？梢哉f搞懂了數(shù)組你就搞懂了算法競(jìng)賽的一大半。這篇文章我想從數(shù)組的內(nèi)存本質(zhì)講起把它在枚舉、雙指針、前綴和、樹狀數(shù)組、矩陣處理、動(dòng)態(tài)規(guī)劃優(yōu)化這些高頻場(chǎng)景里的用法拆開聊一遍順帶把那些比賽中經(jīng)常踩的坑也一并交代清楚。不管你是剛?cè)腴T的選手還是藍(lán)橋杯、ICPC、CCPC備考中的進(jìn)階黨這篇文章都適合拿來當(dāng)作一份“數(shù)組使用手冊(cè)”反復(fù)翻。1. 數(shù)組為什么是算法競(jìng)賽的“地基”從內(nèi)存模型說起要理解數(shù)組在競(jìng)賽中的分量先得想明白一個(gè)問題為什么幾乎所有的算法題解里最終都是“開一個(gè)數(shù)組”來解決問題答案不在于數(shù)組本身有多復(fù)雜而在于它背后那段連續(xù)的、固定大小的內(nèi)存。1.1 連續(xù)內(nèi)存帶來的O(1)隨機(jī)訪問數(shù)組最核心的性質(zhì)是下標(biāo)尋址。C/C里a[i]本質(zhì)上就是*(a i * sizeof(T))Java里雖然多了一層對(duì)象包裝但底層依然是一段連續(xù)空間Python的list也是動(dòng)態(tài)數(shù)組訪問依然是O(1)。這意味著什么意味著你可以用下標(biāo)在瞬間定位到任意一個(gè)位置不需要像鏈表那樣從頭遍歷。這個(gè)性質(zhì)在算法競(jìng)賽里被用到了極致。比如二分查找、快速排序、堆排序它們?nèi)家蕾囉跀?shù)組的隨機(jī)訪問能力。你想象一下如果每次查中間元素都要O(n)地走過去那二分操作一次就是O(n)整個(gè)算法就退化成了笑話。數(shù)組的連續(xù)內(nèi)存還帶來一個(gè)額外的紅利緩存友好?，F(xiàn)代CPU加載數(shù)據(jù)時(shí)按緩存行一次加載64字節(jié)數(shù)組的連續(xù)存儲(chǔ)能把相鄰元素一起拉進(jìn)緩存遍歷時(shí)極少缺頁(yè)。而鏈表節(jié)點(diǎn)散落在內(nèi)存各處每次訪問都大概率觸發(fā)緩存未命中。所以同樣是O(n)的遍歷數(shù)組往往比鏈表快好幾倍。競(jìng)賽里數(shù)據(jù)規(guī)模一大這種常數(shù)級(jí)別的差距就足以決定你是AC還是TLE。1.2 空間換時(shí)間的底層邏輯哈希與布爾的“偽哈?！睌?shù)組另一個(gè)被低估的能力是拿空間換時(shí)間。最經(jīng)典的就是“布爾數(shù)組當(dāng)哈希表用”——開一個(gè)bool vis[MAXN]如果值x出現(xiàn)過就標(biāo)記vis[x] true查詢時(shí)直接O(1)判斷。這比任何哈希表都省常數(shù)因?yàn)檫B哈希函數(shù)都不用算。我當(dāng)年在藍(lán)橋杯做一道題需要判斷兩個(gè)序列是否同構(gòu)第一反應(yīng)是搞個(gè)map后來發(fā)現(xiàn)數(shù)據(jù)范圍只有10^5直接開一個(gè)int idMap[100005]用數(shù)組的下標(biāo)做鍵瞬間O(1)映射代碼短了一半不止。同樣的思路也出現(xiàn)在字符串處理里。比如判斷字母是否出現(xiàn)開一個(gè)int count[26]用字符減去a得到下標(biāo)一行代碼搞定統(tǒng)計(jì)。這簡(jiǎn)直是競(jìng)賽里的“萬金油”操作從統(tǒng)計(jì)詞頻、判斷字母異位詞到滑動(dòng)窗口的窗口字符計(jì)數(shù)全都在用這個(gè)套路。提示數(shù)組哈希的硬限制是值域必須可控。如果數(shù)據(jù)范圍是10^9甚至更大開數(shù)組就不現(xiàn)實(shí)那時(shí)候才輪到std::unordered_map出場(chǎng)。所以比賽中拿到題目先看數(shù)據(jù)范圍這一步往往決定了你要不要開大數(shù)組。2. 競(jìng)賽中最常見的數(shù)組應(yīng)用范式從暴力到優(yōu)雅數(shù)組本身不產(chǎn)生算法但它幾乎是每個(gè)基礎(chǔ)算法的“容器”。這里我把競(jìng)賽中出現(xiàn)頻率最高、最實(shí)用的幾類數(shù)組用法串一遍你會(huì)發(fā)現(xiàn)很多看起來“高級(jí)”的算法拆到底層都是數(shù)組操作的組合。2.1 暴力枚舉與剪枝數(shù)組最直接的用法暴力枚舉是競(jìng)賽中最樸素也最不能被忽視的方法。完全枚舉的思想很簡(jiǎn)單把所有的可能都試一遍看哪個(gè)滿足條件。配合數(shù)組枚舉就變得非常直接——用多重循環(huán)遍歷數(shù)組組合再用一個(gè)結(jié)果數(shù)組收集合法答案。但純暴力往往過不了大數(shù)據(jù)真正厲害的是在枚舉過程中加入剪枝。剪枝的本質(zhì)是“提前判斷這條路肯定走不通所以不再往下走”。判斷的依據(jù)是什么就是你當(dāng)前狀態(tài)在數(shù)組里反映出來的信息。舉個(gè)例子有一類“N皇后”問題你要在N×N棋盤上放N個(gè)皇后。最暴力的方法是C(N2, N)種組合規(guī)模稍微一大就爆炸。但如果我們用一維數(shù)組col[10]記錄每一列是否已放皇后再配合兩個(gè)對(duì)角線數(shù)組diag1[20]、diag2[20]用行列和行-列做下標(biāo)每放一個(gè)皇后就O(1)檢查位置是否沖突不沖突才繼續(xù)遞歸。這就是用數(shù)組實(shí)現(xiàn)了剪枝條件復(fù)雜度從組合爆炸降到了指數(shù)級(jí)但可接受的范圍。再比如子集枚舉。給定一個(gè)數(shù)組要求所有子集的和。你可以用二進(jìn)制位枚舉把狀態(tài)壓成一個(gè)整數(shù)每一位表示“選/不選”然后對(duì)每個(gè)狀態(tài)用一個(gè)循環(huán)累加對(duì)應(yīng)下標(biāo)的元素。這種寫法把數(shù)組下標(biāo)和位運(yùn)算結(jié)合起來是最樸素的“狀態(tài)壓縮”思想。2.2 雙指針與滑動(dòng)窗口讓數(shù)組遍歷從O(n2)降到O(n)如果說暴力枚舉是數(shù)組用法的基礎(chǔ)版那雙指針就是數(shù)組用法的進(jìn)階版。雙指針的核心在于利用數(shù)組下標(biāo)單調(diào)性避免無效的重復(fù)掃描。最常見的場(chǎng)景是“有序數(shù)組兩數(shù)之和”。給定一個(gè)升序數(shù)組找出兩個(gè)數(shù)使和為target。暴力是兩層循環(huán)O(n2)但用雙指針一個(gè)指頭一個(gè)指尾根據(jù)當(dāng)前和與target的關(guān)系決定哪邊移動(dòng)一趟就能掃完降到O(n)?；瑒?dòng)窗口是雙指針的一種變體常用于子數(shù)組/子串問題。比如“最長(zhǎng)無重復(fù)字符子串”你需要維護(hù)窗口的左右邊界用數(shù)組lastPos[128]記錄每個(gè)字符上一次出現(xiàn)的位置。右指針每擴(kuò)展一格就查數(shù)組更新左指針位置同時(shí)更新答案。整個(gè)過程每個(gè)元素只進(jìn)出窗口一次復(fù)雜度O(n)。這里有一個(gè)關(guān)鍵心得滑動(dòng)窗口能用的前提是窗口的約束條件具有單調(diào)性——窗口變大時(shí)滿足性可能被破壞窗口變小時(shí)滿足性只會(huì)更容易。如果你發(fā)現(xiàn)題目要求“子數(shù)組滿足某種性質(zhì)”先想想把右指針往右移、左指針往右移時(shí)這個(gè)性質(zhì)的變化是不是單調(diào)的。如果是那大概率就能用滑動(dòng)窗口。2.3 前綴和與差分靜態(tài)區(qū)間查詢的高效解法前綴和是數(shù)組上最經(jīng)典的空間換時(shí)間操作。一維前綴和數(shù)組pre[i]表示原數(shù)組前i個(gè)元素的和預(yù)處理O(n)查詢?nèi)我鈪^(qū)間[l, r]的和只需要pre[r] - pre[l-1]O(1)搞定。如果你需要頻繁查詢區(qū)間和、區(qū)間平均值、區(qū)間乘積取模前綴和幾乎是必選方案。擴(kuò)展到二維二維前綴和sum[i][j]表示以(1,1)為左上角、(i,j)為右下角的矩形區(qū)域總和查詢?nèi)我饩匦螀^(qū)域的和就用容斥原理四個(gè)格子算一下。這個(gè)在矩陣類題目中極其常用比如“求矩陣中所有和為K的子矩陣數(shù)量”先做二維前綴和再枚舉上下邊界配合哈希存中間結(jié)果能把暴力O(n?)優(yōu)化到O(n3)。差分?jǐn)?shù)組則是前綴和的“逆運(yùn)算”。相鄰兩個(gè)原數(shù)組元素相減得到差分?jǐn)?shù)組diff[i] a[i] - a[i-1]區(qū)間[l, r]加上一個(gè)值v時(shí)只需要diff[l] v、diff[r1] - v最后前綴和還原原數(shù)組。這個(gè)技巧在“區(qū)間更新、最后統(tǒng)一查詢”的題目里堪稱神器。比如你有10^5次操作每次給一個(gè)區(qū)間的所有元素加一個(gè)數(shù)最后問每個(gè)元素的值。直接模擬是O(nm)用差分?jǐn)?shù)組就是O(nm)。3. 數(shù)組作為高級(jí)數(shù)據(jù)結(jié)構(gòu)的載體樹狀數(shù)組與單調(diào)結(jié)構(gòu)數(shù)組不僅能直接解決問題還能作為更高級(jí)數(shù)據(jù)結(jié)構(gòu)的“肉身”。很多看起來很玄乎的結(jié)構(gòu)拆開一看都是建立在數(shù)組之上。3.1 樹狀數(shù)組用普通數(shù)組實(shí)現(xiàn)的快速動(dòng)態(tài)前綴和樹狀數(shù)組Fenwick Tree是我最喜歡的數(shù)據(jù)結(jié)構(gòu)之一因?yàn)樗榷逃謴?qiáng)。你需要維護(hù)一個(gè)數(shù)組支持兩種操作單點(diǎn)修改、前綴和查詢而且都要求O(log n)。樹狀數(shù)組的做法是用一個(gè)tree[]數(shù)組存“分塊和”修改和查詢時(shí)通過i i (-i)這種位運(yùn)算更新下標(biāo)。為什么它能做到O(log n)因?yàn)閠ree[i]維護(hù)的是原數(shù)組中(i - lowbit(i), i]這段區(qū)間的和查詢前綴和時(shí)把若干個(gè)二進(jìn)制段拼起來。樹狀數(shù)組的代碼不過十幾行但在競(jìng)賽里用處極廣逆序?qū)τ?jì)數(shù)、動(dòng)態(tài)區(qū)間第K大、二維樹狀數(shù)組處理矩陣動(dòng)態(tài)修改查詢……它都能勝任。注意樹狀數(shù)組下標(biāo)必須從1開始。如果你習(xí)慣0基數(shù)組要么在構(gòu)建時(shí)整體1偏移要么使用i (i (-i))時(shí)確保不會(huì)出現(xiàn)0死循環(huán)。這個(gè)0基/1基的坑我在初學(xué)時(shí)吃過不少虧。3.2 單調(diào)棧與單調(diào)隊(duì)列數(shù)組下標(biāo)即棧/隊(duì)列指針單調(diào)棧和單調(diào)隊(duì)列聽起來像是“數(shù)據(jù)結(jié)構(gòu)”但在競(jìng)賽實(shí)現(xiàn)里它們大部分時(shí)候就是用數(shù)組模擬的。為什么不用std::stack因?yàn)槟阈枰焖侔聪聵?biāo)訪問棧內(nèi)元素而且很多題需要把棧內(nèi)元素的下標(biāo)記錄下來作為答案的一部分手寫數(shù)組棧更靈活。單調(diào)棧最典型的應(yīng)用是“尋找下一個(gè)更大元素”——給一個(gè)數(shù)組對(duì)每個(gè)位置找右邊第一個(gè)比它大的元素。做法是從右往左掃維護(hù)一個(gè)單調(diào)遞減的棧棧里存的是數(shù)組下標(biāo)。當(dāng)前元素入棧前把所有比它小的元素彈出彈出的過程其實(shí)就是在回答“誰是這些元素的下一個(gè)更大元素”——就是當(dāng)前元素。答案可以放在一個(gè)ans[]數(shù)組里根據(jù)彈出的下標(biāo)回填。整個(gè)過程O(n)比暴力O(n2)快了不止一個(gè)量級(jí)。單調(diào)隊(duì)列則常用于滑動(dòng)窗口最值問題。經(jīng)典題“滑動(dòng)窗口最大值”要求每個(gè)窗口內(nèi)快速取最大值。用deque當(dāng)然可以但競(jìng)賽選手更習(xí)慣直接用數(shù)組q[]當(dāng)雙端隊(duì)列頭指針head、尾指針tail維護(hù)一個(gè)窗口內(nèi)元素下標(biāo)的單調(diào)隊(duì)列。每個(gè)元素最多進(jìn)隊(duì)出隊(duì)一次總復(fù)雜度O(n)。這個(gè)能力在處理大量線掃描題時(shí)簡(jiǎn)直好用。3.3 并查集與圖遍歷數(shù)組就是鄰接表的基本形態(tài)并查集本質(zhì)上就是兩個(gè)數(shù)組parent[]記錄每個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)rank[]或size[]記錄樹的高度/大小。路徑壓縮是在查詢時(shí)把沿途節(jié)點(diǎn)的父節(jié)點(diǎn)直接指向根按秩合并是把小樹掛到大樹上。這些操作全部是數(shù)組賦值和比較。并查集看起來簡(jiǎn)單但處理連通性、最小生成樹的Kruskal算法、甚至離線查詢帶權(quán)并查集、可撤銷并查集全都離不開它。圖的存儲(chǔ)也大量依賴數(shù)組。鄰接表在競(jìng)賽里最常見的實(shí)現(xiàn)不是vectorvectorint而是“鏈?zhǔn)角跋蛐恰薄胔ead[]記錄每個(gè)點(diǎn)的首條邊下標(biāo)用edge[]數(shù)組存所有邊每條邊帶to、weight、next三個(gè)字段。這種存儲(chǔ)方式不僅省內(nèi)存而且遍歷一個(gè)點(diǎn)的所有鄰邊時(shí)只需一個(gè)for循環(huán)順著next往下找在深度優(yōu)先遍歷和廣度優(yōu)先遍歷時(shí)性能極佳。4. 多維數(shù)組與矩陣問題的實(shí)戰(zhàn)套路競(jìng)賽里有一大類題目直接和二維數(shù)組杠上矩陣旋轉(zhuǎn)、迷宮尋路、島嶼數(shù)量、掃雷游戲、生命游戲……這類題的特點(diǎn)是邏輯本身不復(fù)雜但邊界處理、方向控制、狀態(tài)記錄非?？简?yàn)對(duì)數(shù)組的掌控力。我把它們單獨(dú)拎出來講是因?yàn)檫@里的套路非常固定掌握之后可以直接套用。4.1 二維數(shù)組的遍歷與邊界處理二維數(shù)組的遍歷本質(zhì)仍然是下標(biāo)運(yùn)算但坑在于邊界。假設(shè)矩陣是m行n列合法的下標(biāo)范圍是0 i m、0 j n。幾乎所有矩陣題都會(huì)用到“四方向”或“八方向”遍歷這時(shí)候預(yù)先定義方向數(shù)組是省事又安全的方法int dx[4] {-1, 1, 0, 0}; int dy[4] {0, 0, -1, 1}; for (int d 0; d 4; d) { int nx x dx[d]; int ny y dy[d]; if (nx 0 || nx m || ny 0 || ny n) continue; // 越界判斷 // 繼續(xù)處理 }這樣的好處是代碼統(tǒng)一改方向個(gè)數(shù)時(shí)只需改數(shù)組和循環(huán)次數(shù)。我見過很多新手寫四個(gè)if判斷方向又長(zhǎng)又容易漏尤其八方向時(shí)更崩潰。4.2 矩陣旋轉(zhuǎn)、翻轉(zhuǎn)與原地操作的核心技巧矩陣旋轉(zhuǎn)90度這類題最直觀的想法是開一個(gè)新二維數(shù)組把原[i][j]賦值到新位置。但很多題目要求原地旋轉(zhuǎn)這時(shí)候可以用“兩次翻轉(zhuǎn)代替旋轉(zhuǎn)”的技巧先水平翻轉(zhuǎn)上下對(duì)稱交換行再沿主對(duì)角線翻轉(zhuǎn)轉(zhuǎn)置兩步組合就能實(shí)現(xiàn)順時(shí)針旋轉(zhuǎn)90度。這個(gè)技巧避免復(fù)雜的四次循環(huán)坐標(biāo)映射代碼極短、不易出錯(cuò)。如果你真想直接推導(dǎo)坐標(biāo)映射記住順時(shí)針旋轉(zhuǎn)90度后原matrix[i][j]會(huì)到新位置matrix[j][n-1-i]。這組公式在題解里經(jīng)常出現(xiàn)但推導(dǎo)不如“兩次翻轉(zhuǎn)”直觀。我自己傾向于用翻轉(zhuǎn)法尤其是矩陣不是正方形時(shí)翻轉(zhuǎn)法依然通用。4.3 網(wǎng)格類搜索問題Flood Fill與狀態(tài)記錄“島嶼數(shù)量”這類問題要求你遍歷網(wǎng)格中相連的陸地。經(jīng)典做法是DFS或BFS但無論哪種都需要一個(gè)visited數(shù)組標(biāo)記每個(gè)格子是否訪問過。這里有個(gè)空間優(yōu)化技巧如果允許修改原數(shù)組可以直接把訪問過的1改成0省掉visited數(shù)組。但要注意這要求題目不關(guān)心原始數(shù)據(jù)的保留。如果后續(xù)還要用原矩陣就不能這么干。DFS在網(wǎng)格上的實(shí)現(xiàn)要小心遞歸棧深度。一個(gè)1000×1000的網(wǎng)格全是陸地遞歸深度可能達(dá)到10^6級(jí)別直接棧溢出。所以網(wǎng)格規(guī)模較大時(shí)優(yōu)先用顯式隊(duì)列的BFS或者用自己維護(hù)的棧進(jìn)行迭代DFS不要裸遞歸。5. 數(shù)組與字符串、動(dòng)態(tài)規(guī)劃的深度結(jié)合數(shù)組和字符串、動(dòng)態(tài)規(guī)劃的結(jié)合是競(jìng)賽進(jìn)階的必經(jīng)之路。很多看起來完全不相干的算法內(nèi)里都是數(shù)組在支撐。5.1 KMP的next數(shù)組字符串匹配中的數(shù)組思想KMP算法是字符串匹配的經(jīng)典算法核心是next[]數(shù)組——它記錄了模式串每個(gè)位置的最長(zhǎng)相等前后綴長(zhǎng)度。當(dāng)匹配失敗時(shí)不是從頭開始重新匹配而是根據(jù)next[]把模式串向右滑動(dòng)到合適位置。這個(gè)過程本質(zhì)上是利用數(shù)組預(yù)先計(jì)算的信息避免重復(fù)掃描。初學(xué)KMP時(shí)最容易犯的錯(cuò)是next數(shù)組的求法搞混。直接模式串自己做匹配求next很容易漏掉邊界條件。我的建議是先背下求next的模板理解了“j是當(dāng)前已匹配前綴長(zhǎng)度”這個(gè)含義后再試著推導(dǎo)幾遍。別急著理解所有細(xì)節(jié)先會(huì)用多寫幾道匹配題回頭再看原理就順了。5.2 滾動(dòng)數(shù)組將O(n2)空間壓到O(n)的關(guān)鍵技術(shù)動(dòng)態(tài)規(guī)劃里如果狀態(tài)轉(zhuǎn)移只依賴前一行或前一列完全沒必要開二維數(shù)組。滾動(dòng)數(shù)組的思路是用一維數(shù)組不斷覆蓋舊值或者用兩個(gè)一維數(shù)組交替使用把空間復(fù)雜度從O(n2)降到O(n)。競(jìng)賽里空間限制有時(shí)很緊張滾動(dòng)數(shù)組往往能救你一命。但滾動(dòng)數(shù)組有個(gè)風(fēng)險(xiǎn)覆蓋順序搞錯(cuò)會(huì)污染狀態(tài)。比如0/1背包問題內(nèi)層循環(huán)必須從大到小枚舉容量因?yàn)閐p[i][c]依賴的是dp[i-1][c-w]如果從小到大更新dp[c-w]可能已經(jīng)是“本次物品已放入”的狀態(tài)了。這個(gè)方向問題只有親自推過一遍才會(huì)真正記住我建議你在草稿紙上畫一個(gè)二維表格標(biāo)出每個(gè)格子依賴哪些格子再?zèng)Q定循環(huán)方向。5.3 記憶化搜索狀態(tài)數(shù)組的設(shè)計(jì)思路記憶化搜索適合那種狀態(tài)多、轉(zhuǎn)移復(fù)雜的遞歸問題。做法是開一個(gè)數(shù)組dp[state]記錄某個(gè)狀態(tài)的結(jié)果遞歸時(shí)先查表算完再寫表避免重復(fù)子問題。這其實(shí)就是“自頂向下的動(dòng)態(tài)規(guī)劃”。狀態(tài)數(shù)組的設(shè)計(jì)是整個(gè)解法的靈魂。比如“走迷宮最短路徑”可以用dist[x][y]記錄從起點(diǎn)到(x,y)的最短距離數(shù)位DP則需要dp[pos][state]配合limit標(biāo)記狀壓DP則用dp[mask]記錄每個(gè)子集狀態(tài)的最優(yōu)值。設(shè)計(jì)狀態(tài)數(shù)組時(shí)問自己三個(gè)問題這個(gè)狀態(tài)需要哪些維度每個(gè)維度的取值范圍多大狀態(tài)之間怎么轉(zhuǎn)移把這三個(gè)問題想清楚了DP題就成功了一大半。6. 競(jìng)賽中數(shù)組使用的高頻坑位與選型建議數(shù)組雖簡(jiǎn)單競(jìng)賽里因數(shù)組出問題的案例卻數(shù)不勝數(shù)。我把高頻坑位總結(jié)成清單每條都是我用WA和RE換來的教訓(xùn)。6.1 數(shù)組越界和初始化80%的RE與WA來源越界訪問是最隱蔽的錯(cuò)誤之一。C/C不檢查數(shù)組邊界越界讀可能返回垃圾值越界寫則可能破壞其他變量甚至直接段錯(cuò)誤。比賽中遇到“本地正常、提交RE”的情況優(yōu)先懷疑數(shù)組越界。初始化的坑更多。全局變量默認(rèn)零初始化但局部數(shù)組不初始化就是垃圾值。很多選手寫int cnt[100005];在函數(shù)內(nèi)部忘了清空后果是數(shù)據(jù)互相污染。我的習(xí)慣是所有數(shù)組能開全局就開全局一是自動(dòng)清零二是避免棧溢出如果必須在局部用立刻memset(cnt, 0, sizeof(cnt))清一次。還有兩個(gè)常見邊界錯(cuò)誤循環(huán)里用還是直接決定是否越界差分?jǐn)?shù)組在r1處做減法時(shí)如果r1等于數(shù)組長(zhǎng)度要保證數(shù)組多開一位。6.2 時(shí)間與空間復(fù)雜度競(jìng)賽中如何估計(jì)數(shù)組大小在競(jìng)賽里開數(shù)組前先算算最壞情況需要多大空間。拿int類型舉例1個(gè)int占4字節(jié)數(shù)組大小為10^6 ≈ 4MB。如果題目?jī)?nèi)存限制256MB理論上能開約6×10^7個(gè)int。但實(shí)際比賽中除了數(shù)組還要留出調(diào)用棧、臨時(shí)變量、STL容器的空間所以安全系數(shù)建議留一半以上。還有一個(gè)經(jīng)驗(yàn)看到n 10^5二維數(shù)組就要小心了——10^10個(gè)int需要40GB肯定爆內(nèi)存這時(shí)候要么換算法要么用一維數(shù)組手動(dòng)模擬二維索引。6.3 不同語(yǔ)言中數(shù)組的差異與選型思路競(jìng)賽里用得最多的是C數(shù)組性能最好但需要手動(dòng)管理內(nèi)存和邊界。Java的數(shù)組是對(duì)象操作簡(jiǎn)便但內(nèi)存開銷大一些并且Arrays.sort對(duì)基本類型數(shù)組用快排、對(duì)對(duì)象數(shù)組用歸并排序時(shí)要留意。Python的list是動(dòng)態(tài)數(shù)組配合切片操作非常爽但常數(shù)較大純算法題沖極限數(shù)據(jù)時(shí)比較吃力有時(shí)需要改用array模塊或直接用bytearray。我個(gè)人的選型建議是追求極致性能時(shí)用C并且多用STL提供的vector、array、string本質(zhì)也是動(dòng)態(tài)數(shù)組來減少手寫錯(cuò)誤開發(fā)效率優(yōu)先時(shí)用Python刷題但要有心理準(zhǔn)備——同樣的O(n log n)算法Python在10^6這個(gè)量級(jí)就可能逼近時(shí)間上限。盡量不要混用語(yǔ)言競(jìng)賽現(xiàn)場(chǎng)切換語(yǔ)言的成本遠(yuǎn)比你想象的高。數(shù)組這個(gè)結(jié)構(gòu)說它簡(jiǎn)單它確實(shí)沒有復(fù)雜的指針變換和遞歸結(jié)構(gòu)說它難它能變化出前綴和、差分、樹狀數(shù)組、單調(diào)隊(duì)列、滾動(dòng)數(shù)組這樣一大串進(jìn)階玩法。我見過太多同學(xué)一開始就盯著“高級(jí)算法”學(xué)等做題時(shí)才發(fā)現(xiàn)自己連數(shù)組都處理不好——邊界錯(cuò)了、空間爆了、初始化沒清。與其追求套路多不如先把數(shù)組這一層打扎實(shí)。你越往后學(xué)越會(huì)發(fā)現(xiàn)每一個(gè)精巧的算法背后站著的都是這個(gè)最樸素的“地基”。