用一个数组当"小本本"，随手记下每个数字的状态——出现过没有、出现了几次、被标记过没有。
很多问题需要反复"查一下某个数字之前出现过没有""数一下某个数字出现了几次"。如果每次都要重新扫一遍所有数据去查，会很慢——更聪明的办法是：开一个数组，用下标对应数值本身，把"这个数值的状态"直接存在对应的格子里。要查的时候，直接用数值当下标去访问数组，一步到位，不用再扫一遍。
其实 1.8 节的筛法已经用过这个思路了——isComposite 数组和 minPrimeFactor 数组，下标就是数字本身，格子里存的是"这个数被标记过没有""这个数的最小质因子是谁"。这一节把这个技巧从筛法里单独拎出来，看看它还能解决哪些问题。
最常见的用法：统计每个值各出现了多少次。比如统计字符串 "hello world" 里每个字母出现的次数——开一个大小为 26 的数组，下标 0~25 分别对应 a~z，每遇到一个字母，就把对应格子的计数加一。
| 1 | string s = "hello world"; |
| 2 | int count[26] = {0}; // 26个字母各自的计数器，初始全是0 |
| 3 | for (char ch : s) |
| 4 | { |
| 5 | if (ch >= 'a' && ch <= 'z') // 跳过空格等非字母字符 |
| 6 | { |
| 7 | count[ch - 'a']++; // 字符转下标，对应格子加一 |
| 8 | } |
| 9 | } |
ch - 'a' 这一步眼熟吗？1.6 节进制转换时用过几乎一样的写法（s[i] - '0' 把字符变成数字）。这里同样是利用字符本身的编码顺序——'a' 到 'z' 在内存里是连续排列的，相减就能得到"这是第几个字母"，直接拿来当数组下标。有时候不需要数"出现了几次"，只需要知道"出现过没有"——这时候数组里存的不是计数，而是一个简单的 true/false。经典场景：判断一个数组里有没有重复的数字。
| 1 | int arr[] = {3, 1, 4, 1, 5, 9, 2, 6}; |
| 2 | bool seen[10] = {false}; // 数组里的数字都在0~9之间 |
| 3 | for (int x : arr) |
| 4 | { |
| 5 | if (seen[x]) // 这个数之前已经出现过 |
| 6 | { |
| 7 | cout << "第一个重复的数字是: " << x << endl; |
| 8 | break; |
| 9 | } |
| 10 | seen[x] = true; // 标记这个数已经出现过 |
| 11 | } |
seen[x] 就行，不需要把整个数组从头扫一遍去比较，这正是数组标记法比"逐个比较"快的原因。再看一个稍微反过来用的例子：1 到 8 之间本该有 8 个不同的数，现在给出了其中 7 个：1 2 4 5 6 7 8，找出缺的是哪一个。思路是：先把"出现过的数"都标记一下，再扫一遍 1 到 8，没被标记过的那个就是答案。
| 1 | int n = 8; |
| 2 | int nums[] = {1, 2, 4, 5, 6, 7, 8}; // 缺了一个数 |
| 3 | bool appeared[9] = {false}; |
| 4 | |
| 5 | // 第一遍：把出现过的数字都标记一下 |
| 6 | for (int x : nums) |
| 7 | { |
| 8 | appeared[x] = true; |
| 9 | } |
| 10 | |
| 11 | // 第二遍：找出没被标记过的那个数 |
| 12 | for (int i = 1; i <= n; i++) |
| 13 | { |
| 14 | if (!appeared[i]) |
| 15 | { |
| 16 | cout << "缺失的数字是: " << i << endl; |
| 17 | } |
| 18 | } |
1~8，发现下标 3 对应的格子没被标记——缺失的数字就是 3。这种"先标记、再扫一遍找空缺"的两段式写法，是数组标记法非常典型的应用模式。| 用法 | 数组存的内容 | 典型场景 |
|---|---|---|
| 计数标记 | 整数（出现的次数） | 统计字母/数字出现频率 |
| 布尔标记 | true / false（出现过没有） | 判断重复、找缺失的数字 |
| 筛法标记 | true / false 或具体数值（如最小质因子） | 1.8 节的埃氏筛、线性筛 |
visited 数组（标记搜索时哪些位置已经走过）——记住这个思路，比记住某一道具体题目的代码更重要。