AcWing语法基础课第四讲"数组"，前前后后我过了两遍。第一遍觉得简单，变量、循环都学完了，数组不就是"开一块空间存一堆数"吗？真正开始刷题才发现，数组这章才是前面所有语法知识的第一次汇合——它帮你建立"连续内存""下标边界""批量操作"这些概念，而这些概念直接决定你后面学字符串、结构体、指针，甚至STL的时候是顺畅还是反复翻车。这篇笔记是我比较完整的总结，包含数组的存储原理、各种初始化方式、二维数组与字符数组的细节，以及memset、fill这类批量操作的坑，最后会复盘几道典型练习题的边界问题。适合正在学C++语法基础的同学、准备蓝桥杯或者刚开始在AcWing、洛谷刷题的新手参考，看到的是"数组能做什么"，但更重要的是"数组的边界在哪里"。
1. 数组的底层逻辑：连续内存、固定长度与下标0的来历
1.1 数组在内存里就是一段连续空间
数组的定义大家都会背，"相同类型元素的集合"，但真正关键的是它的存储方式：在内存中开辟一段连续空间，每个元素占同样多的字节数。正因为连续，你才能用a[i]直接命中第 i 个元素，不用从头一个个找。a[i]的地址等价于：
数组起始地址 + i * sizeof(元素类型)举个例子，int a[10]起始地址假设是0x1000，每个 int 占 4 个字节，那么：
a[0]在0x1000a[1]在0x1004a[3]在0x100C
这个地址计算是固定时间的，也就是常说的 O(1) 随机访问。这是数组一切应用的底层基础，也是它和链表最大的区别——链表的节点在内存里是散的，访问第 k 个必须从头走 k 步。
1.2 为什么下标从 0 开始
下标本质是"偏移量"，不是"序号"。a[i]的寻址公式里用的是i而不是i - 1，所以第一个元素自然对应i = 0。如果下标从 1 开始，每次访问都要额外做一次减 1 运算，虽然现代编译器也能优化掉，但设计上就是从 0 开始最自然。
不过这带来一个新手常见问题：很多题目习惯从 1 开始编号，比如"有 n 个数，第 1 个数是……"，不少人就直接写int a[100]，然后从a[1]存到a[n]。这完全没问题，a[0]空着不用就行。但你要时刻清楚自己用的是"自然编号"还是"下标"：如果你从a[1]开始存，循环就是for (int i = 1; i <= n; i++)，这时候n是有效的，a[n]是最后那个元素；如果你从a[0]开始存，循环就是for (int i = 0; i < n; i++)，a[n-1]才是最后一个。这两种写法混着用，是最常见的 WA 来源。
1.3 sizeof 测数组长度：一个隐蔽的陷阱
sizeof(a)返回整个数组占用的字节总数，sizeof(a[0])是一个元素的大小，两者相除得到元素个数，这是写循环时常用的一段代码：
int a[100]; int len = sizeof(a) / sizeof(a[0]); // len == 100但这个写法有一个大坑：数组作为参数传给函数时，会退化成指针。看这段代码：
void f(int a[]) { // 这里 sizeof(a) 是指针大小，不是数组大小 int len = sizeof(a) / sizeof(a[0]); // 在64位系统上结果是 8 / 4 = 2 }void f(int a[])和void f(int* a)是等价的，函数内部拿到的只是一个指针，8 个字节（64位系统），用sizeof测出来的"长度"完全是错的。所以要么把长度作为参数传进去，要么在函数外先算好长度再传入。C++17 里的std::size(a)也只能用在数组还没有退化的地方，别指望它救你。
2. 一维数组的声明与初始化：这些写法背后的差异
2.1 长度必须是编译期常量
int a[10]里的 10 在编译时就得确定。下面的写法在标准 C++ 里是不合法的：
int n; cin >> n; int a[n]; // 标准C++不支持，属于GCC的VLA扩展原因是数组在栈上分配，编译器必须知道具体字节数才能生成代码。也是因为这一点，后面才需要vector这样的动态数组——这是后话，但你可以先记住：定长数组的长度必须是编译期常量。
还有一个环境问题要提醒：全局数组开在数据段，局部数组开在栈上，而栈空间默认只有几 MB。局部开int a[1000000]也就是 4MB，勉强可以；但如果开到几百万甚至上千万 int，就会爆栈，程序直接崩。这种情况要么把数组放到全局，要么用动态内存。
2.2 各种初始化方式的缺省值
C++ 数组初始化写法很多，每种效果不一样，我整理了一个对照：
| 写法 | 结果 |
|---|---|
int a[10];（局部变量） | 随机脏数据，值是栈上残留的东西 |
int a[10] = {}; | 全部初始化为 0 |
int a[10] = {0}; | 第一个是 0，其余也是 0 |
int a[10] = {1, 2}; | 前两个是 1、2，后面全是 0 |
int a[] = {1, 2, 3}; | 编译器自动推导长度为 3 |
全局/静态int a[10]; | 不写初始化也是全 0 |
初学者最容易踩的坑是第三种和第四种：= {0}和= {1, 2}这类写法，只有显式写出来的那几个位置被赋值，剩余位置自动补 0。有人以为int a[10] = {1};会把 10 个元素全设成 1，这是错的，只有a[0]是 1，其他都是 0。
这个规则在竞赛里经常用。比如统计字母出现次数，开一个int cnt[26]，如果它是全局变量就不用手动清零；如果放在main里面，必须显式初始化成{}或者用后面的memset。
2.3 越界访问不会报错，但后果很严重
数组越界是最典型的 C/C++ 安全隐患。a[100]访问的是起始地址往后第 101 个 int 的位置，编译器根本不会帮你检查。实际后果有三种：
- 运气好，访问到一段还没被使用的内存，程序"假装正常"；
- 访问到别的变量的地址，悄悄把别人的数据改了，产生难以排查的 bug；
- 直接访问到非法地址，触发段错误（Segmentation Fault），程序崩溃。
竞赛里最经典的"数组开小了"就是这么来的：题面说 n 最大 100，你开了a[100]，循环里却访问了a[100]，而最后一个合法下标是 99。这种 RE 很难一眼看出来，我的习惯是开数组时留余量，比如最大 100 就开a[105]或a[110]，多几个字节几乎不占空间，但能省掉很多调试时间。
3. 二维数组的内存排列与遍历顺序
3.1 二维数组本质上一维连续内存
int a[3][4]在内存里就是 12 个 int 连续排着，行与行之间没有空隙。a[2][3]的地址 = 起始地址 +(2 * 4 + 3) * 4字节。这种"按行优先"的排列方式，决定了编译器必须知道列数才能计算偏移。
这也解释了一个常见的语法规定：函数参数写二维数组时，第二维不能省略：
void calc(int a[][4]); // 合法，可以通过列数计算行偏移 void calc(int a[][]); // 不合法，不知道每行多长初学者可能会问，为什么第一维可以省而第二维不行？因为数组名作为参数退化后，编译器只知道首地址，要访问a[i][j]必须先算出它离首地址多远，这个距离依赖列数，不依赖行数。
3.2 遍历顺序影响缓存命中
二维数组连续排列带来的实际影响是遍历顺序。下面两种写法，逻辑上结果一样：
// 按行遍历：先固定行，内层逐列走 for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) sum += a[i][j]; // 按列遍历：先固定列，内层逐行走 for (int j = 0; j < m; j++) for (int i = 0; i < n; i++) sum += a[i][j];按行遍历时，每次访问的地址都是连续的，CPU 缓存命中率高；按列遍历时，每次跳跃 m 个 int 的大小，缓存频繁失效，数据量一大，耗时差距可能拉到几倍。这个细节在算法竞赛的"卡常"优化里经常被拿出来说，写的时候养成按行遍历的习惯就好。
3.3 二维数组的初始化与典型应用
二维数组初始化同样支持按行给值：
int a[3][4] = { {1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12} };可以省略某些行，省略的部分自动补 0。使用场景就太常见了：矩阵运算、棋盘、迷宫地图、动态规划的 DP 表格。尤其后面学动态规划，基本每个题都要开一个二维表，dp[i][j]表示某个状态。如果现在就把二维数组的内存模型画清楚了，后面看状态转移方程会轻松很多。
4. 字符数组与字符串：'\0' 的约定让多少新手翻过车
4.1 字符数组的两种初始化方式
字符串在 C/C++ 里不是一种原生类型，而是"约定以\0结尾的字符数组"。这个\0是 ASCII 码为 0 的字符，用来标记字符串的结束位置。看这两个写法：
char s1[] = "abc"; // 实际长度是4，末尾自动补 '\0' char s2[3] = {'a','b','c'}; // 没有 '\0's1有 4 个字符：'a'、'b'、'c'、'\0'。s2只有三个字符，没地方写'\0'。如果之后把s2当字符串用，比如调用strlen(s2)，它会一直往后读，直到在内存里撞到一个字节为 0 的位置为止，这是未定义行为，结果完全不可控。
还要注意单引号和双引号的区别：'a'是字符，"a"是字符串字面量，后者实际上包含'a'和'\0'两个字符。
4.2 输入函数的选择：cin、scanf、getline
往字符数组里读内容，方式不同行为差别很大：
cin >> s或scanf("%s", s)：遇到空格、Tab、换行就停止，读不了带空格的句子；cin.getline(s, 100)：读一整行，包括空格，最多读 99 个字符并自动补'\0'；fgets(s, 100, stdin)：也读整行，但会保留末尾的换行符，需要自己处理。
竞赛里更常用scanf和printf，因为格式控制直接、性能也更好。一个容易记错的地方：scanf("%s", s)里s前面不用加&，因为数组名本身在表达式里就会退化成首地址指针。
char s[100]; scanf("%s", s); // 正确，s 已经是地址 scanf("%s", &s); // 也能工作，但类型上不对，不推荐4.3 字符函数与常见错误
处理字符数组经常用到<cstring>里的几个函数：
strlen(s)返回'\0'之前的字符个数，所以char s[100] = "hello";的strlen(s)是 5，而sizeof(s)是 100；strcpy(dest, src)把src的内容（包括末尾'\0'）复制到dest，但它不检查目标容量，dest小了就直接越界写；strcmp(a, b)比较字符串大小，返回负值、0 或正值。
最常见的坑有两个。一是strcpy越界：目标数组开小了，src一长就崩，尤其是循环里拼接字符串时更容易发生。二是自己构造字符串忘记补'\0'，比如把数字转成字符串：
char s[20]; int len = 0; while (x > 0) { s[len++] = '0' + x % 10; x /= 10; } s[len] = '\0'; // 这一行不能省少了最后一行，strlen(s)或者printf("%s", s)就会一直读到内存里某个碰巧为 0 的字节为止。这种 bug 排查起来特别费劲，因为错误不在眼前这几行，而在"你违反了约定"。
5. 批量操作三件套：memset、fill与memcpy的正确边界
5.1 memset 按字节填充的原理
memset的功能是把一段内存的每一个字节都设成同一个值：
memset(a, 0, sizeof(a)); // 把数组a的每个字节设为0为什么memset(a, 0, sizeof(a))能把整个 int 数组清零？因为 int 占 4 个字节，把这 4 个字节都设成 0，整个 int 自然就是 0。同理，memset(a, -1, sizeof(a))可以，因为 -1 的二进制表示是所有位全 1，4 个字节全是0xFF，合成一个 int 还是 -1。
但memset(a, 1, sizeof(a))就完全不是你想的样子了。每个字节被设成0x01，一个 int 的 4 个字节合起来是0x01010101，也就是十进制 16843009，不是 1。这是数组操作里出现频率最高的低级错误，没有之一。
所以正确结论是：memset只能可靠地设置 0 或 -1，以及一些按字节有意义的值。
5.2 竞赛里的 0x3f3f3f3f 无穷大
很多算法题需要把数组初始化为一个"很大的数"，用来表示无穷大。竞赛圈常用的写法是：
memset(dist, 0x3f, sizeof(dist));为什么是0x3f而不是更大的数？因为memset按字节填充，每个字节设为0x3f，一个 int 四个字节就变成0x3f3f3f3f。这个数的十进制是 1061109567，大约是 10 亿，比 int 上限约 21 亿小不少，但又足够大，两个这样的大数相加不会溢出 int。最短路、最小生成树这类算法里，初始化dist、f数组时非常常用。
对比一下直接用memset(a, 0x7f, sizeof(a))，得到的是0x7f7f7f7f，约 21 亿，两个相加就直接溢出变成负数，反而破坏了比较逻辑。所以0x3f是实践检验出来的安全选择。
5.3 fill 和 memcpy：按元素赋值与按字节复制
memset只适合填 0、-1 这类特殊值，如果想把整个数组填成 5、10 这种普通整数，应该用<algorithm>里的fill：
fill(a, a + 10, 5); // 把a[0]到a[9]全部设为5fill是按元素赋值的，填什么值都行。注意区间是左闭右开，a + 10表示结束位置，这个位置本身不会被赋值。
memcpy则是按字节复制：
memcpy(b, a, sizeof(a)); // 把数组a完整复制到b第三个参数是字节数，不是元素个数。如果写成memcpy(b, a, 10)而a是 int 数组，那实际上只复制了 10 个字节，也就是 2.5 个 int，绝大多数情况下是个致命错误。
把这三个操作放一起对比：
| 函数 | 原理 | 适用场景 | 典型坑 |
|---|---|---|---|
memset | 按字节填充 | 清零、设为 -1、设为 0x3f | 填普通整数得到错误结果 |
fill | 按元素赋值 | 任意值批量填充 | 区间写错导致赋值范围不对 |
memcpy | 按字节复制 | 同类型数组整体复制 | 第三个参数误写元素个数 |
6. 题目复盘：翻转、去重与冒泡排序的边界细节
6.1 数组翻转：双指针而不是再开一个数组
翻转是最基础的操作，比如把a[0]和a[n-1]对调，a[1]和a[n-2]对调。最自然的思路是双指针：
int i = 0, j = n - 1; while (i < j) { int t = a[i]; a[i] = a[j]; a[j] = t; i++; j--; }边界条件是i < j而不是i <= j，因为当i == j时中间那个元素不需要和自己交换。有人喜欢写for循环，i <= n / 2之类，也不难，但双指针的写法更通用，后面学链表翻转等内容时能直接复用这个思路。
这里也可以顺便熟悉std::swap：
swap(a[i], a[j]);本质和临时变量交换一样，但代码更简洁。
6.2 数组去重：先想清楚是否要求保持顺序
去重是一类很常见的题，"数组去重"这个热搜词下面的解法很多，但关键在于题目是否要求保持原顺序。
如果要求保持原顺序，最直接的做法是用标记数组：
bool vis[10010] = {}; int n = 0; for (int i = 0; i < m; i++) { if (!vis[a[i]]) { vis[a[i]] = true; res[n++] = a[i]; } }如果允许排序后去重，就简单得多：
sort(a, a + n); int m = 0; for (int i = 0; i < n; i++) { if (i == 0 || a[i] != a[i - 1]) { a[m++] = a[i]; } }注意sort的区间是左闭右开[a, a + n)。去重后数组长度变成 m，后面的元素即使仍然存在也不用管。
6.3 冒泡排序的完整代码与循环边界
冒泡排序是数组章节最经典的循环边界练习题，完整的写法如下：
void bubbleSort(int a[], int n) { for (int i = 0; i < n - 1; i++) { bool swapped = false; for (int j = 0; j < n - i - 1; j++) { if (a[j] > a[j + 1]) { int t = a[j]; a[j] = a[j + 1]; a[j + 1] = t; swapped = true; } } if (!swapped) break; // 这一趟没有交换，说明已经有序 } }两个边界最容易写错的地方：
- 外层
i < n - 1：最多需要 n - 1 趟，因为剩下最后一个元素时不用再排； - 内层
j < n - i - 1：每一趟结束后，最后 i + 1 个元素已经就位，不需要再比较，所以上限要减掉 i 再加一个偏移，写成n - i - 1。如果写成j < n - 1，每次都会访问a[j + 1]，当j = n - 2时访问a[n - 1]，越界。
swapped标志位是优化关键：如果某一趟从头到尾没有发生交换，说明数组已经有序，直接退出，最坏情况 O(n²)，最好情况能到 O(n)。
7. 定长限制的出路：动态数组与vector的使用取舍
7.1 为什么需要动态数组
定长数组在这个场景下很难受：输入规模不确定，或者在程序运行过程中需要不断追加元素。比如读入一串整数，个数未知，你没法提前确定数组长度。有人会开一个很大的数组先放着，比如a[1000005]，这在知道上限时完全可行，也是一种常见做法。但如果上限都不知道，或者需要反复增删，就需要动态数组。
C++ 里最常用的动态数组容器是vector：
vector<int> a; // 空数组 a.push_back(1); // 在末尾追加 a.push_back(5); cout << a.size(); // 2如果一开始就知道大概规模，可以直接提前指定长度：
vector<int> a(n, 0); // 长度为n，全部初始化为0vector内部帮你管理内存，扩容时采用倍增策略，平均下来每次追加的代价是 O(1)，实际竞赛中性能也够用。
7.2 二维vector与其他选择
二维动态数组可以这样构造：
vector<vector<int>> g(n, vector<int>(m, 0)); // n行m列，全部为0这相当于开了一个动态的 n 行 m 列矩阵，适合行数列数运行时才确定的情况。和原生二维数组相比，语法上多了模板嵌套，但灵活性高很多。
我的个人习惯是这样的：
| 场景 | 选择 | 理由 |
|---|---|---|
| 题面给了明确上限，追求速度 | 原生数组 | 直接、快，不用考虑扩容 |
| 不确定大小，需要追加元素 | vector | 自动管理内存，支持动态增长 |
| 行数或列数运行时才确定的二维结构 | vector<vector<int>> | 灵活，避免手动管理内存 |
| 需要极高性能且内存吃紧的卡常题 | 原生数组 | 少了容器层的开销 |
有一点要注意：vector<int>::size()返回的是size_t，是无符号类型。如果写成for (int i = 0; i < a.size(); i++)，i是int而a.size()是size_t，常见情况下没问题，但a为空时a.size()是 0，int和size_t比较会有隐式转换警告。稳妥写法是for (int i = 0; i < (int)a.size(); i++)，或者用size_t i = 0。
7.3 指针数组与数组指针（简单扩展）
学完数组之后，后面学指针时还会遇到两个名字很像的东西：
int* p[10]是指针数组：这个数组有 10 个元素，每个元素都是int*指针，常用于替代二维字符数组；int (*p)[10]是指向数组的指针：p是一个指针，指向一个含有 10 个 int 的数组。
《语法基础课》阶段不用深究，但先有个印象，后面接触指针不会觉得突兀。这里只提一点：二维数组名传给函数时，本质上就是"指向数组的指针"，这和你看到的"第二维不能省略"规则是同一个原理。
数组这一讲，看起来全是基础语法，但决定后面刷题效率的，恰恰是那些最不起眼的边界：循环最后一次执行的 i 是多少，a[n]到底能不能碰，memset能不能填 1，字符数组末尾有没有'\0'。我自己在 AcWing 刷题时，WA 和 RE 绝大多数不是思路问题，而是数组边界和初始化细节翻车。分享两个我目前一直在用的习惯：写循环前先想清楚"这个下标最后停在哪"，再动手；开数组时一律多开几个位置，n最大 100 就开a[110]，数组初始化要么{}要么memset，不依赖局部变量的随机值。这些小习惯看起来笨，但能省下大把调试时间。
