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