很多同学刚接触算法竞赛时，第一反应是去啃各种“高大上”的算法——图论、动态规划、网络流、字符串匹配。但真正让我意识到“地基”重要性的，是一次比赛中因为数组开小导致半小时调不出错误、最后发现是边界问题的惨痛教训。数组，这个最基础、最不起眼的数据结构，恰恰是算法竞赛里几乎所有解法的落脚点。你写的每一份代码，本质上都在操作数组：状态转移存数组、邻接表存数组、哈希冲突解决也依赖数组。可以说，搞懂了数组，你就搞懂了算法竞赛的一大半。
这篇文章我想从数组的内存本质讲起，把它在枚举、双指针、前缀和、树状数组、矩阵处理、动态规划优化这些高频场景里的用法拆开聊一遍，顺带把那些比赛中经常踩的坑也一并交代清楚。不管你是刚入门的选手，还是蓝桥杯、ICPC、CCPC备考中的进阶党，这篇文章都适合拿来当作一份“数组使用手册”反复翻。
1. 数组为什么是算法竞赛的“地基”：从内存模型说起
要理解数组在竞赛中的分量，先得想明白一个问题：为什么几乎所有的算法题解里，最终都是“开一个数组”来解决问题？答案不在于数组本身有多复杂，而在于它背后那段连续的、固定大小的内存。
1.1 连续内存带来的O(1)随机访问
数组最核心的性质是下标寻址。C/C++里，a[i]本质上就是*(a + i * sizeof(T))，Java里虽然多了一层对象包装，但底层依然是一段连续空间，Python的list也是动态数组，访问依然是O(1)。这意味着什么？意味着你可以用下标在瞬间定位到任意一个位置，不需要像链表那样从头遍历。
这个性质在算法竞赛里被用到了极致。比如二分查找、快速排序、堆排序，它们全都依赖于数组的随机访问能力。你想象一下，如果每次查中间元素都要O(n)地走过去，那二分操作一次就是O(n)，整个算法就退化成了笑话。
数组的连续内存还带来一个额外的红利：缓存友好。现代CPU加载数据时按缓存行一次加载64字节，数组的连续存储能把相邻元素一起拉进缓存，遍历时极少缺页。而链表节点散落在内存各处，每次访问都大概率触发缓存未命中。所以同样是O(n)的遍历，数组往往比链表快好几倍。竞赛里数据规模一大，这种常数级别的差距就足以决定你是AC还是TLE。
1.2 空间换时间的底层逻辑：哈希与布尔的“伪哈希”
数组另一个被低估的能力，是拿空间换时间。最经典的就是“布尔数组当哈希表用”——开一个bool vis[MAXN]，如果值x出现过就标记vis[x] = true，查询时直接O(1)判断。这比任何哈希表都省常数，因为连哈希函数都不用算。
我当年在蓝桥杯做一道题，需要判断两个序列是否同构，第一反应是搞个map，后来发现数据范围只有10^5，直接开一个int idMap[100005]，用数组的下标做键，瞬间O(1)映射，代码短了一半不止。
同样的思路也出现在字符串处理里。比如判断字母是否出现，开一个int count[26]，用字符减去'a'得到下标，一行代码搞定统计。这简直是竞赛里的“万金油”操作，从统计词频、判断字母异位词，到滑动窗口的窗口字符计数，全都在用这个套路。
提示：数组哈希的硬限制是值域必须可控。如果数据范围是10^9甚至更大，开数组就不现实，那时候才轮到
std::unordered_map出场。所以比赛中拿到题目先看数据范围，这一步往往决定了你要不要开大数组。
2. 竞赛中最常见的数组应用范式：从暴力到优雅
数组本身不产生算法，但它几乎是每个基础算法的“容器”。这里我把竞赛中出现频率最高、最实用的几类数组用法串一遍，你会发现很多看起来“高级”的算法，拆到底层都是数组操作的组合。
2.1 暴力枚举与剪枝：数组最直接的用法
暴力枚举是竞赛中最朴素也最不能被忽视的方法。完全枚举的思想很简单：把所有的可能都试一遍，看哪个满足条件。配合数组，枚举就变得非常直接——用多重循环遍历数组组合，再用一个结果数组收集合法答案。
但纯暴力往往过不了大数据，真正厉害的是在枚举过程中加入剪枝。剪枝的本质是“提前判断这条路肯定走不通，所以不再往下走”。判断的依据是什么？就是你当前状态在数组里反映出来的信息。
举个例子，有一类“N皇后”问题，你要在N×N棋盘上放N个皇后。最暴力的方法是C(N², N)种组合，规模稍微一大就爆炸。但如果我们用一维数组col[10]记录每一列是否已放皇后，再配合两个对角线数组diag1[20]、diag2[20]（用行+列和行-列做下标），每放一个皇后就O(1)检查位置是否冲突，不冲突才继续递归。这就是用数组实现了剪枝条件，复杂度从组合爆炸降到了指数级但可接受的范围。
再比如子集枚举。给定一个数组，要求所有子集的和。你可以用二进制位枚举，把状态压成一个整数，每一位表示“选/不选”，然后对每个状态用一个循环累加对应下标的元素。这种写法把数组下标和位运算结合起来，是最朴素的“状态压缩”思想。
2.2 双指针与滑动窗口：让数组遍历从O(n²)降到O(n)
如果说暴力枚举是数组用法的基础版，那双指针就是数组用法的进阶版。双指针的核心在于：利用数组下标单调性，避免无效的重复扫描。
最常见的场景是“有序数组两数之和”。给定一个升序数组，找出两个数使和为target。暴力是两层循环O(n²)，但用双指针，一个指头一个指尾，根据当前和与target的关系决定哪边移动，一趟就能扫完，降到O(n)。
滑动窗口是双指针的一种变体，常用于子数组/子串问题。比如“最长无重复字符子串”，你需要维护窗口的左右边界，用数组lastPos[128]记录每个字符上一次出现的位置。右指针每扩展一格，就查数组更新左指针位置，同时更新答案。整个过程每个元素只进出窗口一次，复杂度O(n)。
这里有一个关键心得：滑动窗口能用的前提是窗口的约束条件具有单调性——窗口变大时满足性可能被破坏，窗口变小时满足性只会更容易。如果你发现题目要求“子数组满足某种性质”，先想想把右指针往右移、左指针往右移时，这个性质的变化是不是单调的。如果是，那大概率就能用滑动窗口。
2.3 前缀和与差分：静态区间查询的高效解法
前缀和是数组上最经典的空间换时间操作。一维前缀和数组pre[i]表示原数组前i个元素的和，预处理O(n)，查询任意区间[l, r]的和只需要pre[r] - pre[l-1]，O(1)搞定。如果你需要频繁查询区间和、区间平均值、区间乘积取模，前缀和几乎是必选方案。
扩展到二维，二维前缀和sum[i][j]表示以(1,1)为左上角、(i,j)为右下角的矩形区域总和，查询任意矩形区域的和就用容斥原理四个格子算一下。这个在矩阵类题目中极其常用，比如“求矩阵中所有和为K的子矩阵数量”，先做二维前缀和，再枚举上下边界，配合哈希存中间结果，能把暴力O(n⁴)优化到O(n³)。
差分数组则是前缀和的“逆运算”。相邻两个原数组元素相减得到差分数组diff[i] = a[i] - a[i-1]，区间[l, r]加上一个值v时，只需要diff[l] += v、diff[r+1] -= v，最后前缀和还原原数组。这个技巧在“区间更新、最后统一查询”的题目里堪称神器。比如你有10^5次操作，每次给一个区间的所有元素加一个数，最后问每个元素的值。直接模拟是O(nm)，用差分数组就是O(n+m)。
3. 数组作为高级数据结构的载体：树状数组与单调结构
数组不仅能直接解决问题，还能作为更高级数据结构的“肉身”。很多看起来很玄乎的结构，拆开一看都是建立在数组之上。
3.1 树状数组：用普通数组实现的快速动态前缀和
树状数组（Fenwick Tree）是我最喜欢的数据结构之一，因为它既短又强。你需要维护一个数组支持两种操作：单点修改、前缀和查询，而且都要求O(log n)。树状数组的做法是用一个tree[]数组存“分块和”，修改和查询时通过i += i & (-i)这种位运算更新下标。
为什么它能做到O(log n)？因为tree[i]维护的是原数组中(i - lowbit(i), i]这段区间的和，查询前缀和时把若干个二进制段拼起来。树状数组的代码不过十几行，但在竞赛里用处极广：逆序对计数、动态区间第K大、二维树状数组处理矩阵动态修改查询……它都能胜任。
注意：树状数组下标必须从1开始。如果你习惯0基数组，要么在构建时整体
+1偏移，要么使用i + (i & (-i))时确保不会出现0死循环。这个0基/1基的坑，我在初学时吃过不少亏。
3.2 单调栈与单调队列：数组下标即栈/队列指针
单调栈和单调队列听起来像是“数据结构”，但在竞赛实现里，它们大部分时候就是用数组模拟的。为什么不用std::stack？因为你需要快速按下标访问栈内元素，而且很多题需要把栈内元素的下标记录下来作为答案的一部分，手写数组栈更灵活。
单调栈最典型的应用是“寻找下一个更大元素”——给一个数组，对每个位置找右边第一个比它大的元素。做法是从右往左扫，维护一个单调递减的栈，栈里存的是数组下标。当前元素入栈前，把所有比它小的元素弹出，弹出的过程其实就是在回答“谁是这些元素的下一个更大元素”——就是当前元素。答案可以放在一个ans[]数组里，根据弹出的下标回填。整个过程O(n)，比暴力O(n²)快了不止一个量级。
单调队列则常用于滑动窗口最值问题。经典题“滑动窗口最大值”要求每个窗口内快速取最大值。用deque当然可以，但竞赛选手更习惯直接用数组q[]当双端队列，头指针head、尾指针tail维护一个窗口内元素下标的单调队列。每个元素最多进队出队一次，总复杂度O(n)。这个能力在处理大量线扫描题时简直好用。
3.3 并查集与图遍历：数组就是邻接表的基本形态
并查集本质上就是两个数组：parent[]记录每个节点的父节点，rank[]或size[]记录树的高度/大小。路径压缩是在查询时把沿途节点的父节点直接指向根，按秩合并是把小树挂到大树上。这些操作全部是数组赋值和比较。并查集看起来简单，但处理连通性、最小生成树的Kruskal算法、甚至离线查询（带权并查集、可撤销并查集）全都离不开它。
图的存储也大量依赖数组。邻接表在竞赛里最常见的实现不是vector<vector<int>>，而是“链式前向星”——用head[]记录每个点的首条边下标，用edge[]数组存所有边，每条边带to、weight、next三个字段。这种存储方式不仅省内存，而且遍历一个点的所有邻边时只需一个for循环顺着next往下找，在深度优先遍历和广度优先遍历时性能极佳。
4. 多维数组与矩阵问题的实战套路
竞赛里有一大类题目直接和二维数组杠上：矩阵旋转、迷宫寻路、岛屿数量、扫雷游戏、生命游戏……这类题的特点是逻辑本身不复杂，但边界处理、方向控制、状态记录非常考验对数组的掌控力。我把它们单独拎出来讲，是因为这里的套路非常固定，掌握之后可以直接套用。
4.1 二维数组的遍历与边界处理
二维数组的遍历本质仍然是下标运算，但坑在于边界。假设矩阵是m行n列，合法的下标范围是0 <= i < m、0 <= j < n。几乎所有矩阵题都会用到“四方向”或“八方向”遍历，这时候预先定义方向数组是省事又安全的方法：
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; // 越界判断 // 继续处理 }这样的好处是代码统一，改方向个数时只需改数组和循环次数。我见过很多新手写四个if判断方向，又长又容易漏，尤其八方向时更崩溃。
4.2 矩阵旋转、翻转与原地操作的核心技巧
矩阵旋转90度这类题，最直观的想法是开一个新二维数组，把原[i][j]赋值到新位置。但很多题目要求原地旋转，这时候可以用“两次翻转代替旋转”的技巧：先水平翻转（上下对称交换行），再沿主对角线翻转（转置），两步组合就能实现顺时针旋转90度。这个技巧避免复杂的四次循环坐标映射，代码极短、不易出错。
如果你真想直接推导坐标映射，记住顺时针旋转90度后，原matrix[i][j]会到新位置matrix[j][n-1-i]。这组公式在题解里经常出现，但推导不如“两次翻转”直观。我自己倾向于用翻转法，尤其是矩阵不是正方形时，翻转法依然通用。
4.3 网格类搜索问题：Flood Fill与状态记录
“岛屿数量”这类问题要求你遍历网格中相连的陆地。经典做法是DFS或BFS，但无论哪种都需要一个visited数组标记每个格子是否访问过。这里有个空间优化技巧：如果允许修改原数组，可以直接把访问过的'1'改成'0'，省掉visited数组。但要注意：这要求题目不关心原始数据的保留。如果后续还要用原矩阵，就不能这么干。
DFS在网格上的实现要小心递归栈深度。一个1000×1000的网格，全是陆地，递归深度可能达到10^6级别，直接栈溢出。所以网格规模较大时，优先用显式队列的BFS，或者用自己维护的栈进行迭代DFS，不要裸递归。
5. 数组与字符串、动态规划的深度结合
数组和字符串、动态规划的结合，是竞赛进阶的必经之路。很多看起来完全不相干的算法，内里都是数组在支撑。
5.1 KMP的next数组：字符串匹配中的数组思想
KMP算法是字符串匹配的经典算法，核心是next[]数组——它记录了模式串每个位置的最长相等前后缀长度。当匹配失败时，不是从头开始重新匹配，而是根据next[]把模式串向右滑动到合适位置。这个过程本质上是利用数组预先计算的信息避免重复扫描。
初学KMP时，最容易犯的错是next数组的求法搞混。直接模式串自己做匹配求next，很容易漏掉边界条件。我的建议是：先背下求next的模板，理解了“j是当前已匹配前缀长度”这个含义后，再试着推导几遍。别急着理解所有细节，先会用，多写几道匹配题，回头再看原理就顺了。
5.2 滚动数组：将O(n²)空间压到O(n)的关键技术
动态规划里，如果状态转移只依赖前一行（或前一列），完全没必要开二维数组。滚动数组的思路是用一维数组不断覆盖旧值，或者用两个一维数组交替使用，把空间复杂度从O(n²)降到O(n)。竞赛里空间限制有时很紧张，滚动数组往往能救你一命。
但滚动数组有个风险：覆盖顺序搞错会污染状态。比如0/1背包问题，内层循环必须从大到小枚举容量，因为dp[i][c]依赖的是dp[i-1][c-w]，如果从小到大更新，dp[c-w]可能已经是“本次物品已放入”的状态了。这个方向问题只有亲自推过一遍才会真正记住，我建议你在草稿纸上画一个二维表格，标出每个格子依赖哪些格子，再决定循环方向。
5.3 记忆化搜索：状态数组的设计思路
记忆化搜索适合那种状态多、转移复杂的递归问题。做法是开一个数组dp[state]记录某个状态的结果，递归时先查表，算完再写表，避免重复子问题。这其实就是“自顶向下的动态规划”。
状态数组的设计是整个解法的灵魂。比如“走迷宫最短路径”可以用dist[x][y]记录从起点到(x,y)的最短距离；数位DP则需要dp[pos][state]配合limit标记；状压DP则用dp[mask]记录每个子集状态的最优值。设计状态数组时，问自己三个问题：这个状态需要哪些维度？每个维度的取值范围多大？状态之间怎么转移？把这三个问题想清楚了，DP题就成功了一大半。
6. 竞赛中数组使用的高频坑位与选型建议
数组虽简单，竞赛里因数组出问题的案例却数不胜数。我把高频坑位总结成清单，每条都是我用WA和RE换来的教训。
6.1 数组越界和初始化：80%的RE与WA来源
越界访问是最隐蔽的错误之一。C/C++不检查数组边界，越界读可能返回垃圾值，越界写则可能破坏其他变量，甚至直接段错误。比赛中遇到“本地正常、提交RE”的情况，优先怀疑数组越界。
初始化的坑更多。全局变量默认零初始化，但局部数组不初始化就是垃圾值。很多选手写int cnt[100005];在函数内部，忘了清空，后果是数据互相污染。我的习惯是：所有数组能开全局就开全局，一是自动清零，二是避免栈溢出；如果必须在局部用，立刻memset(cnt, 0, sizeof(cnt))清一次。
还有两个常见边界错误：循环里用<=还是<直接决定是否越界；差分数组在r+1处做减法时，如果r+1等于数组长度，要保证数组多开一位。
6.2 时间与空间复杂度：竞赛中如何估计数组大小
在竞赛里开数组前，先算算最坏情况需要多大空间。拿int类型举例，1个int占4字节，数组大小为10^6 ≈ 4MB。如果题目内存限制256MB，理论上能开约6×10^7个int。但实际比赛中除了数组，还要留出调用栈、临时变量、STL容器的空间，所以安全系数建议留一半以上。
还有一个经验：看到n <= 10^5，二维数组就要小心了——10^10个int需要40GB，肯定爆内存，这时候要么换算法，要么用一维数组手动模拟二维索引。
6.3 不同语言中数组的差异与选型思路
竞赛里用得最多的是C++，数组性能最好，但需要手动管理内存和边界。Java的数组是对象，操作简便，但内存开销大一些，并且Arrays.sort对基本类型数组用快排、对对象数组用归并，排序时要留意。Python的list是动态数组，配合切片操作非常爽，但常数较大，纯算法题冲极限数据时比较吃力，有时需要改用array模块或直接用bytearray。
我个人的选型建议是：追求极致性能时用C++，并且多用STL提供的vector、array、string（本质也是动态数组）来减少手写错误；开发效率优先时用Python刷题，但要有心理准备——同样的O(n log n)算法，Python在10^6这个量级就可能逼近时间上限。尽量不要混用语言，竞赛现场切换语言的成本远比你想象的高。
数组这个结构，说它简单，它确实没有复杂的指针变换和递归结构；说它难，它能变化出前缀和、差分、树状数组、单调队列、滚动数组这样一大串进阶玩法。我见过太多同学一开始就盯着“高级算法”学，等做题时才发现自己连数组都处理不好——边界错了、空间爆了、初始化没清。与其追求套路多，不如先把数组这一层打扎实。你越往后学，越会发现每一个精巧的算法背后，站着的都是这个最朴素的“地基”。