七、数组

前面所有题目都是「读进来、处理、扔掉」。这一页开始，数据要留下来。

为什么需要留下来？因为有些操作必须回头访问前面的数据：找最大值的位置、判断是否递增、排序、统计每个数出现了几次。这些都得先把数据存进数组。

这一页 5 章 25 道题，核心是四个套路：

1. 遍历——用循环把数组走一遍
2. 桶——用下标本身表示数值，这是最巧妙也最常用的技巧
3. 排序——把数据排好，很多问题就自动解决了
4. 前缀和 / 差分——把「区间求和」和「区间修改」从 O(n) 降到 O(1)

最后一个稍难，但它是后面所有区间题的基础，值得花时间。

22. 数组的存取与遍历

22.1 为什么要数组

假设要读 100 个数，然后倒着输出。

不用数组，你只能边读边处理——但倒着输出要求你先记住全部 100 个数，这做不到（不能用 100 个变量）。

int a[105];                    // 声明一个能装 105 个整数的数组
for (int i = 0; i < n; i++) {
    scanf("%d", &a[i]);        // 第 i 个位置放进读到的数
}
for (int i = n - 1; i >= 0; i--) {
    printf("%d ", a[i]);       // 倒着输出
}

a[0]、a[1]、a[2]……每个都是一个独立的变量，用方括号里的数字区分。那个数字叫下标。

为什么开 105 而不是 100？ 因为题目说 n 最大 100，但下标是 0 到 n-1，如果 n 真的等于 100，你要用 a[99]，开 100 刚好够。多开 5 个是保险——

int a[100];
a[100] = 5;      // 越界了！但编译器不拦你

22.2 下标从 0 开始

int a[5] = {10, 20, 30, 40, 50};
//  a[0]=10  a[1]=20  a[2]=30  a[3]=40  a[4]=50

第一个元素是 a[0]，不是 a[1]。 最后一个元素是 a[n-1]，不是 a[n]。

这是初学最容易错的地方。遍历 n 个元素的标准写法：

for (int i = 0; i < n; i++) {      // 注意是 i < n，不是 i <= n
    // 处理 a[i]
}

写成 i <= n 就会访问 a[n]——越界，读到垃圾值。

22.3 遍历：求和、求平均、找最大值

数组的绝大多数操作，都是「用一个循环走一遍」。

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

int mx = a[0];                       // 用第一个元素做初值，最保险
for (int i = 1; i < n; i++) {
    if (a[i] > mx) mx = a[i];
}

注意最大值的初值：用 a[0]，不是 0。 第 13 章讲过这个坑，有了数组之后更简单——直接把第一个元素当初始答案就行，不用 INT_MIN 了。

23. 统计与标记

这一章讲数组最巧妙的一个用法：用下标表示数值。

23.1 桶：下标就是答案

问题：统计每个数出现了几次。

普通思路是「对每个数，遍历一遍数组数一数」，复杂度 O(n²)。更快的做法是开一个「桶」：

int cnt[1005] = {0};           // 桶，初始全 0
for (int i = 0; i < n; i++) {
    int x;
    scanf("%d", &x);
    cnt[x]++;                  // 数值 x 出现一次，就把第 x 个桶 +1
}
// 现在 cnt[7] 就是 7 出现的次数

cnt[x]++ 这一行是本章的灵魂。 它把「数值」直接当成了「下标」，省掉了查找的过程。

桶排序就是由此而来：

for (int i = 0; i <= 最大值; i++) {
    for (int j = 0; j < cnt[i]; j++) printf("%d ", i);
}

从小到大遍历下标，就自然排好序了。复杂度 O(n + 最大值)——比任何比较排序都快，前提是数值范围不大。

int cnt[1005];        // 如果题目给的数最大是 10^9，这个桶直接爆炸

23.2 标记数组：记录「有没有出现过」

有时候不需要计数，只需要知道某个值「出现过没有」：

bool used[1005] = {false};
used[x] = true;                 // 标记 x 出现过
if (used[y]) { /* y 出现过 */ }

bool 数组比 int 数组更合适：意图清楚，而且省内存（每个元素只占 1 字节）。

23.3 预处理：先算好，再查表

有些题要反复问「某个值对应的答案是多少」。每次都重新算太慢，不如先把所有答案算好存起来：

int f[1000005];
for (int i = 1; i <= n; i++) {
    f[i] = f[i-1] + 计算(i);      // 一次算完
}
// 后面直接查 f[x] 就行，O(1)

这种「打表」的思路，在后面动态规划里会变成核心方法。现在先体会一下：用空间换时间。

23.4 差值数组：相邻之间的变化

24. 排序

排序是最常用的操作之一。很多题排完序就做完了——找中位数、找第 k 大、判断重复，都是这样。

24.1 手写排序：选择排序和冒泡排序

选择排序的思路：每一轮找出剩下元素里最小的，放到前面。

for (int i = 0; i < n - 1; i++) {
    int k = i;
    for (int j = i + 1; j < n; j++) {
        if (a[j] < a[k]) k = j;      // 找最小值的下标
    }
    swap(a[i], a[k]);                // 换到前面
}

冒泡排序的思路：相邻两个比较，大的往后换，一轮下来最大的就到了末尾。

for (int i = 0; i < n - 1; i++) {
    for (int j = 0; j < n - 1 - i; j++) {
        if (a[j] > a[j+1]) swap(a[j], a[j+1]);
    }
}

两种都是 O(n²)，n = 1000 时约 100 万次，能过；n = 10 万时就超时了。

先学会手写，是为了理解「排序在干什么」。 实际做题用下一节的 sort。

24.2 sort：直接用标准库

#include <algorithm>          // bits/stdc++.h 已经包含了

sort(a, a + n);               // 从小到大，排 a[0] 到 a[n-1]
sort(a, a + n, greater<int>());  // 从大到小

sort 的复杂度是 O(n log n)，n = 100 万也能在 1 秒内跑完。没有特殊要求就用它，别手写。

注意两个参数是地址区间：a 是起点，a + n 是终点（不是 a + n - 1）。这是「左闭右开」的写法，排的是 a[0] 到 a[n-1]。

排序之后，很多问题会变简单：

• 找中位数 → 排序后取 a[n/2]
• 找第 k 大 → 排序后取 a[n-k]
• 判断有没有重复 → 排序后看相邻是否相等
• 去重 → 排序后跳过相同的

25. 前缀和与差分

这一章讲两个「用一点空间，换大量时间」的技巧。它们看着简单，但是后面所有区间题的基础。

25.1 前缀和：快速求区间和

问题：给一个数组，反复问「第 l 个到第 r 个的和是多少」。

暴力做法每次都要累加，一次 O(n)，问 m 次就是 O(nm)，很容易超时。

前缀和的做法是先算好一个累加数组：

int s[100005];
s[0] = 0;
for (int i = 1; i <= n; i++) {
    s[i] = s[i-1] + a[i];        // s[i] = 前 i 个数的和
}

s[i] 表示前 i 个元素的和。有了它，区间 [l, r] 的和就是：

int sum = s[r] - s[l-1];

O(1) 出答案。原理是「前 r 个的和」减去「前 l-1 个的和」，剩下的正好是第 l 到第 r 个。

注意 s[0] = 0 这个哨兵。 有了它，l = 1 时 s[l-1] 就是 s[0] = 0，公式不用特判。

25.2 差分：快速做区间修改

前缀和的逆操作。问题：把数组的第 l 到第 r 个元素都加上 v，做 m 次，最后输出整个数组。

暴力做法每次改 r-l+1 个元素，O(nm)。差分的做法是只改两个位置：

d[l] += v;
d[r+1] -= v;

然后最后做一次前缀和还原：

int cur = 0;
for (int i = 1; i <= n; i++) {
    cur += d[i];
    a[i] += cur;
}

为什么只改两个位置就够？ 因为做前缀和的时候，d[l] 的 +v 会一直往后传递到 d[r+1] 处的 -v，正好抵消。中间那一段就都被加上了 v。

这是「用两个点表示一个区间」的思想，非常巧妙。

25.3 区间覆盖

26. 数组综合

26.1 最大连续子段和

问题：在一个数组里，找一段连续的子数组，使它们的和最大。

最直接的暴力是三重的（枚举左右端点 + 求和），O(n³)。稍微优化是两重，O(n²)。

但有一遍扫描的做法：

int best = a[0], cur = a[0];
for (int i = 1; i < n; i++) {
    cur = max(a[i], cur + a[i]);      // 要么接着上一段，要么从自己重新开始
    best = max(best, cur);
}

cur = max(a[i], cur + a[i]) 的意思是：如果前面那段的和是负的，还不如从当前这个数重新开始。

这就是贪心的思路——负的历史拖累，不如丢掉。

26.2 双指针

两个下标一起移动，通常一个往右一个也往右，用来处理「连续区间」的问题。

int l = 0, r = 0;
while (r < n) {
    // 加入 a[r]
    while (不满足条件) {
        // 移出 a[l]，l 右移
        l++;
    }
    // 此时 [l, r] 是一个合法区间
    r++;
}

26.3 其他

延伸阅读

服务器上有一整套 OI-Wiki（621 页），是给竞赛选手写的参考手册。下面几页跟这一页相关，但不是每一页都该现在看——标了「现在跳过」的，等以后再说。

• 可以先看：数组 —— 数组的内存布局图。看懂「下标从 0 开始」为什么是 0 而不是 1
• 学完这一页再看：前缀和 & 差分 —— 这章的核心工具，wiki 讲得更系统。差分那半章可以推到第 26 章再看
• 学完这一页再看：排序应用 —— 排序之后能做什么——名次、去重、找中位数
• 学完这一页再看：排序简介 —— 各种排序的复杂度对比。这章用 sort 就够，但知道它内部干了什么不吃亏