哈希思想之数组构造：轻松解决统计与区间问题

对于刚接触算法的同学来说，哈希思想听起来似乎很抽象，但其实用数组实现的哈希思想是最基础、最易上手的算法技巧之一。它核心思路特别简单：用数组的下标当作“键”，数组存储的内容当作“值”，通过这种一一对应的方式，实现数据的快速统计、查询和修改，能轻松解决算法入门中最常见的字母统计、数字计数、区间标记类问题（比如经典的“校门外的树”）。

这种方法无需复杂的容器，仅用基础的数组就能实现，时间复杂度能达到O(n)，效率极高，是算法入门必须掌握的“万能技巧”。

一、核心思想：数组就是最简单的哈希表

我们先回忆数组的基本特性：数组的下标是唯一的、有序的，通过下标可以直接访问对应位置的元素，时间复杂度为O(1)。

而哈希思想的核心，就是建立“键”和“值”的唯一映射关系，让我们能通过键快速找到对应的值。当我们要处理的键是范围明确的整数时，直接用数组就能完美实现这种映射：

• 键：需要统计/标记的目标（比如字母a、数字5、区间位置10），将其转化为连续的整数下标；
• 值：对应键的统计结果/标记状态（比如字母a出现3次、位置10的树是否被砍掉）；
• 数组构造：根据键的范围，定义一个合适大小的数组，初始化后通过遍历目标数据，更新对应下标的值即可。

简单来说，就是把要处理的目标“贴”到数组下标上，用数组内容记录目标的信息，这就是数组版哈希思想的核心。

二、核心步骤：三步构造数组解决问题

无论面对统计类还是区间类问题，用数组实现哈希思想的步骤都是固定的，一共三步，记牢就能直接套用：

步骤1：确定“键”的范围，定义数组

先分析题目中需要处理的目标键是什么，将其转化为整数下标，并确定下标的最小值和最大值，定义一个大小足够的数组（避免下标越界）。

• 比如统计26个英文字母：键是a-z，可转化为0-25的下标（a→0，b→1，…，z→25），数组大小定义为26即可；
• 比如校门外的树：键是道路的位置（0~1000），下标直接用位置数，数组大小定义为1001即可。

步骤2：初始化数组

根据问题需求初始化数组值：

• 统计类问题：初始化为0（表示初始时所有目标的统计数为0）；
• 标记类问题：初始化为特定值（比如校门外的树，初始化为1表示树存在，0表示树被砍掉）。

步骤3：遍历处理数据，更新数组

遍历题目给出的原始数据，将每个目标转化为对应下标，根据问题规则更新数组对应位置的值：

• 统计类：遇到目标，对应下标值+1（比如遇到字母a，arr[0]++）；
• 标记类：遇到目标区间，将区间内的下标值修改为标记状态（比如砍掉0~50的树，将arr[0]~arr[50]设为0）。

步骤4：根据数组结果，输出答案

遍历构造好的数组，根据数组的下标和值，整理出题目要求的答案（比如统计类求每个字母的出现次数，标记类求剩余树的数量）。

这四步是固定模板，所有数组哈希的问题都能按这个流程解决，接下来我们结合入门经典题，手把手教你怎么用。

三、经典应用1：统计类问题——字母出现次数统计

这是算法入门最基础的统计题，也是数组哈希的典型应用，比如题目：输入一个字符串，统计每个小写英文字母出现的次数，按a-z的顺序输出。

解题分析

1. 确定键与数组：目标键是a-z的小写字母，范围固定，将字母转化为0-25的下标（转化公式：下标 = 字符 - 'a'，比如a-'a'=0，b-'a'=1），定义数组int cnt[26] = {0};（大小26，初始化为0，统计次数）；
2. 遍历更新数组：遍历字符串的每个字符，按公式转化为下标，对应位置+1；
3. 输出结果：遍历0-25的下标，输出每个下标对应的值，就是a-z的出现次数。

核心代码（C++）

#include <iostream>
#include <string>
using namespace std;

int main() {
    string s;
    cin >> s;
    // 步骤1+2：定义哈希数组，初始化0，26个下标对应a-z
    int cnt[26] = {0};
    // 步骤3：遍历字符串，更新统计数
    for (char c : s) {
        int idx = c - 'a'; // 字符转下标，核心哈希映射
        cnt[idx]++;
    }
    // 步骤4：遍历数组，输出结果
    for (int i = 0; i < 26; i++) {
        cout << (char)('a' + i) << "：" << cnt[i] << "次" << endl;
    }
    return 0;
}

关键技巧

字符转下标是这类题的核心，利用ASCII码的连续性：小写字母a-z的ASCII码是连续的，减去'a'的ASCII码，就能得到0-25的连续下标；同理，大写字母A-Z可转c-'A'，数字字符0-9可转c-'0'。

四、经典应用2：标记类问题——校门外的树（区间标记与统计）

这是算法入门经典的区间问题，题目原型：校门外有一条长度为L的道路，道路上从0到L有L+1棵树。现在有M次砍树操作，每次操作砍掉区间[start, end]内的所有树，求最后还剩下多少棵树（比如L=1000，M=10）。

解题分析

1. 确定键与数组：目标键是道路的位置（0~L），下标直接用位置数，定义数组int tree[1001] = {1};（大小L+1，初始化为1，1表示树存在，0表示被砍掉）；
2. 遍历更新数组：遍历M次砍树操作，每次拿到[start, end]，将数组中从start到end的下标值设为0；
3. 输出结果：遍历整个数组，统计值为1的元素个数，就是剩余树的数量。

核心代码（C++）

#include <iostream>
using namespace std;

const int MAX_L = 1001; // 道路最大长度1000，数组大小1001

int main() {
    int L, M;
    cin >> L >> M;
    // 步骤1+2：定义哈希数组，初始化1（树存在）
    int tree[MAX_L] = {0};
    for (int i = 0; i <= L; i++) {
        tree[i] = 1;
    }
    // 步骤3：遍历砍树操作，标记区间
    for (int i = 0; i < M; i++) {
        int start, end;
        cin >> start >> end;
        for (int j = start; j <= end; j++) {
            tree[j] = 0; // 砍掉区间内的树，标记为0
        }
    }
    // 步骤4：统计剩余树的数量
    int res = 0;
    for (int i = 0; i <= L; i++) {
        if (tree[i] == 1) {
            res++;
        }
    }
    cout << "剩余树的数量：" << res << endl;
    return 0;
}

拓展思维

这类区间标记问题，用数组哈希将位置作为键，状态作为值，直接通过下标标记区间，替代了复杂的区间存储。如果后续遇到区间恢复问题，也只需将对应下标值改回初始状态即可。

五、数组哈希的适用场景与注意事项

适用场景

数组实现的哈希思想不是万能的，但在算法入门阶段，满足以下条件的问题，用它绝对是最优解：

1. 键能转化为连续的整数：比如26个字母、0~N的位置、固定范围的数字（0~1000、0~10000）；
2. 键的范围明确且不大：比如下标范围0~10000，数组大小能轻松定义，不会出现内存溢出；
3. 需求是简单的统计/标记/查询：比如统计次数、标记存在/不存在、查询某个目标的状态。

注意事项

1. 数组大小要足够，避免下标越界：比如键的范围是0~1000，数组大小至少定义为1001（因为数组下标从0开始）；
2. 键的映射要唯一：确保每个目标只能对应一个下标，一个下标只能对应一个目标，比如不能让a既对应0又对应1；
3. 初始化要正确：统计类初始化为0，标记类根据状态初始化为1/0，避免因初始化错误导致结果出错；
4. 区分“字符”和“数字”：统计字符时，一定要通过ASCII码转化为下标，不能直接用字符作为下标（比如直接用'a'作为下标会因ASCII码值过大导致越界）。

六、拓展：数组哈希的进阶小技巧

掌握了基础用法后，我们可以尝试一些简单的拓展，解决更灵活的问题：

1. 统计大小写字母：定义大小为52的数组，小写字母a-z对应0-25，大写字母A-Z对应26-51（映射公式：大写A-Z→c-'A'+26）；
2. 统计数字和字母混合：定义大小为62的数组，0-9对应0-9，a-z对应10-35，A-Z对应36-61；
3. 区间快速操作：对于大规模的区间标记问题（比如L=1e5），基础的循环标记会超时，可结合差分思想（数组哈希+差分），将区间操作的时间复杂度从O(n)优化为O(1)，这是后续要学习的进阶技巧，但其核心还是数组哈希。

七、总结：数组哈希是算法入门的“敲门砖”

对于刚学算法的同学来说，用数组实现的哈希思想，是从“暴力遍历”到“高效算法”的第一步，它没有复杂的概念，核心就是“下标当键，内容当值”，通过三步固定模板就能解决大部分入门统计和区间问题。

这种方法不仅能帮我们快速解决题目，更重要的是能让我们理解“空间换时间”的算法思想——用一个小小的数组，将原本需要多次遍历的暴力解法，优化为一次遍历的高效解法，这也是后续学习哈希表、字典、差分、前缀和等算法的基础。

在入门阶段，建议大家多做这类题目，把数组哈希的思路练熟，当你能下意识地用数组下标来映射目标时，就已经迈出了算法学习的关键一步。后续遇到键的范围不固定、不连续的问题时，再学习进阶的哈希表（如C++的unordered_map），就能水到渠成了。