数组

题单类型：官方题单

创建人：

ACGO官方

题数：20题

收藏题单

完成度：0/20

数组

1. 数组的介绍

数组是一种用来存放“一组同类型数据”的工具。
可以把它理解成“一排连续的格子”，每个格子放一个数据，并且每个格子都有编号（下标）。

2. 数组的规则

2.1 下标规则

访问数组： $a[i]$
$i$ 必须是“整数表达式”（例如 int / long long），不能是小数
如果数组长度是 $n$ $n$ ，并且下标从 $0$ $0$ 开始：
- 合法范围： $0 \sim n-1$
- 访问 $a[n]$ 是越界（ $RE$ ）

最常用循环写法：

for (int i = 0; i < n; i++) {
    // 使用 a[i]
}

2.2 数组长度规则

数组的写法是：

int a[N];

要求：

$N$ 必须是“常量”（数字，或者 const 常量）
$N$ 要开得足够大，保证不会越界，通常情况下会比题目中给出的数据多一点

例如：

const int N = 200000 + 5;
int a[N];
int b[200005];
const int M = 2e5 + 5;//等价于200000 + 5
int c[M];
int d[2e5 + 5];//报错 , 2e5 + 5 不是一个常数

3. 数组的定义

3.1 全局数组

把数组写在 main 外面：

#include <bits/stdc++.h>
using namespace std;

const int N = 200000 + 5;
int a[N]; // 全局数组

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];
    return 0;
}

全局数组特点：

默认会自动初始化为 $0$ （没赋值也全是 $0$ ）
可以开得比较大（适合 $n$ 很大）
作用范围包含整个程序（哪里都能用）

3.2 局部数组

把数组写在函数里面（例如 main 里）：

int main() {
    int a[1000]; // 局部数组
    int n;
    cin >> n;
    int b[n];
    int c[n + 5];
    ...
}

局部数组的坏处：

不会自动清零
里面是“随机值/垃圾值”，不手动初始化就可能出错。
开太大容易发生错误
例如开到几十万、几百万时，可能直接运行出错（RE）。

强烈建议同学们在竞赛当中使用全局数组！

3.3 数组的输入

数组题基本都要先把数据读进数组。最常见有两种读法：下标从 $0$ 开始、下标从 $1$ 开始。

3.3.1 下标从 $0$ 开始

元素范围： $a[0]\sim a[n-1]$

int n;
cin >> n;
for (int i = 0; i < n; i++) {
    cin >> a[i];
}

3.3.2 下标从 $1$ 开始

元素范围： $a[1]\sim a[n]$
注意：需要保证数组开得足够大，一般开到 $n+5$ 更安全。

int n;
cin >> n;
for (int i = 1; i <= n; i++){ 
    cin >> a[i];
}

优点：有些题用“第 $1$ 个到第 $n$ 个”时更直观。
注意：要小心别访问到 $a[0]$ 或 $a[n+1]$ 。

3.3.3 输入数组时的常见细节

先读 $n$ 再读数组
循环边界不要写错

$0$ 开始：i < n
$1$ 开始：i <= n

数组要开够大
例如 $n\le 2\times 10^5$ ：

const int N = 200000 + 5;
int a[N];

3.3.4 示例

其中， $a$ 数组的下标从 $0$ 开始， $b$ 数组的下标从 $1$ 开始**（请注意区分)**

#include <bits/stdc++.h>
using namespace std;

const int N = 200000 + 5;
int a[N];
int b[N];

int main() {
    int n;
    cin >> n;

    for (int i = 0; i < n; i++){
        cin >> a[i];
    }

    for (int i = 0; i < n; i++) {
        cout << a[i] << " ";
    }
    
    for (int i = 1; i <= n; i++){
        cin >> b[i];
    }

    for (int i = 1; i <= n; i++) {
        cout << b[i] << " ";
    }
    return 0;
}

4. 数组的初始化

4.1 全局数组默认初始化为 $0$

const int N = 10;
int a[N]; // 全局：默认全是 0

4.2 局部数组必须手动初始化（否则是垃圾值）

最常用的两种方式：

方式 $1$ ：循环赋值

int a[10];
for (int i = 0; i < 10; i++) a[i] = 0;

方式 $2$ ：用 {0} 快速清零

int a[10] = {0}; // 局部也能全部变成 0

4.3 指定部分初值，剩下自动补 $0$

int a[6] = {1, 2, 3}; // 后面自动补 0

4.4 初始化函数

作为拓展，后续我们常常会使用 $\text{memset()}$ 函数来初始化数组

4.4.1 基本用法

$\text{memset(地址, 值, 字节数)}$
它会把从“地址”开始的连续内存，一共“字节数”这么多字节，都设置成同一个“值”。

最常见写法（把整个数组清零）：

int a[1000];
memset(a, 0, sizeof(a));   // 把 a 的所有字节都设为 0，其中 sizeof(a) 会返回 a 数组所占的字节数

4.4.2 适用范围

$\text{memset()}$ 适合初始化：

char 数组（字符串等）
int 数组清零（设为 0）
long long 数组清零（设为 0）
bool 数组清零（设为 0）
int 数组设置成极大值/极小值

4.4.3 常见用法示例

1）清零：

int a[1000];
memset(a, 0, sizeof(a));

2）把 char 数组变成全 'A'（注意这里填的是字符的 ASCII 值）：

char s[10];
memset(s, 'A', sizeof(s)); // 每个位置都是 'A'

3）把 int 数组初始化为 -1：

int a[1000];
memset(a, -1, sizeof(a));  // 常用于“未访问/不存在”的标记

4）把 int 数组初始化为极大值：

int a[1000];
memset(a, 0x3f , sizeof(a));  // 其意义是把 int 的4个字节全部变成0011 1111，也就是把所有值变成0011 1111 0011 1111 0011 1111 0011 1111 (B)
cout << a[0]; // a[0] = 1061109567

5）把int 数组初始化为极小值：

int a[1000];
memset(a, -0x3f , sizeof(a));  // 其意义是把 int 的4个字节全部变成1011 1111，也就是把所有值变成1011 1111 1011 1111 1011 1111 1011 1111 (B)
cout << a[0]; // a[0] = -1044266559

4.4.4 重要注意事项

$\text{memset()}$ 是按“字节”填充，不是按“整数”填充。
所以除了 $0$ 和 $-1$ 这种非常特殊的值以外，不要用 memset 给 int 数组设置成 1、2、100 之类。

例如（错误示例）：

int a[5];
memset(a, 1, sizeof(a)); // 错！不会得到 a[i]=1，而是变成0000 0001 0000 0001 0000 0001 0000 0001 (B)
cout << a[0];//  a[0] = 16843009

原因：每个字节都变成 1，最后 int 里的值会变成一个很大的数，不是 1。

如果你想把 int 数组设成某个普通数字（比如全设为 5），请用循环：

int a[1000];
for (int i = 0; i < 1000; i++) a[i] = 5;

4.4.5 头文件

使用 $\text{memset()}$ 需要包含：

#include <cstring>（或者使用万能头文件 #include <bits/stdc++.h> ）

5. 数组的用处

数组的核心价值：

当你要处理“很多个同类型的数据”，并且这些数据要按顺序 / 按编号访问时，用数组最方便。

5.1 存一堆数据，后面反复用

很多题都会先给你 $n$ 个数，接下来要你做很多操作：求最大值、求和、排序、统计……
如果不存起来，你就只能“读一个算一个”，很多操作做不了。

例题：

A82859.数组逆序重放

A29930.合唱队形

A30707.【一维数组】【入门】计算书费

A66.陶陶摘苹果

5.2 快速按下标访问

数组最大的优势之一：

想看第 $i$ 个元素，直接访问 a[i]即可。

这在需要“频繁访问某个位置”的题里非常重要。

例题：

A82868.向量点积计算

5.3 统计出现次数

你可以用数组当“桶”：

cnt[x] 表示数字 $x$ 出现了多少次

例题：

A21209.梦中的统计

A30709.【一维数组】【入门】校门外的树

A82871.团队竞赛

【前置知识点】
1、循环

【后置衔接知识点】
1、字符串
2、二维数组

【思维导图】

【题目知识点分类】

数组

数组