钦州市网站建设_网站建设公司_一站式建站_seo优化

深度解析：空间换时间的艺术 —— 从区间频率查询看哈希与二分

在处理大规模数据查询时，性能优化是核心。LeetCode 2080 题《区间内查询数字的频率》是一个绝佳的案例。本文将通过“哈希表预处理”与“二分查找”两大维度，带你领略现代 C++ 的解题美学。

一、 哈希表：构建高效的“档案库”

在本题中，如果我们每次查询都遍历区间，时间复杂度是 O(N)，面对 10^5 级别的查询必然超时。我们的策略是构建一个 unordered_map<int, vector>。

1. 结构深度解析

这个结构可以理解为一个“分类索引”：

• Key (键)：数组中出现的具体数值（如 33）。
• Value (值)：一个升序排列的 vector，记录了该数值在原数组中出现的所有下标（如 [1, 3, 5]）。

2. 增删改查的实战用法

在 C++ 中，unordered_map 是基于哈希表实现的，其平均操作效率为 O(1)：

• 增/改：

  pos[val].push_back(index); // 若 val 不存在，会自动创建一个空的 vector 并添加 index

• 查（标准定式）：
  为了避免不必要的插入（副作用），推荐使用 find() 配合 end() 进行检查：

  auto it = pos.find(target); if (it != pos.end()) { // 找到了，it->second 就是我们要的下标 vector }

• 删：

pos.erase(val); // 即可瞬间根据键删除对应的内容。

3. 性能关键

在查询函数中，你会看到这样的代码：

auto& a = it->second;

• 为什么要加 &？
• 如果不加 &，程序会把整个 vector 拷贝一遍。加上 & 后，a 仅仅是原哈希表中 vector 的一个别名，没有任何数据复制。在处理海量数据时，这一个字符之差就是 TLE（超时）与 AC（通过）的分水岭。

二、 二分查找

有了有序的下标数组后，核心任务就是：在有序数组中，统计有多少个下标落在 [left, right] 之间。此时，std::lower_bound 和 std::upper_bound 就派上用场了。

1. lower_bound：定位左边界

• 功能：在有序序列中找到第一个 大于等于 (>=) 给定值的元素位置。
• 应用：lower_bound(a, left) 帮我们找到第一个落在区间内的有效下标位置。

2. upper_bound：定位右边界

• 功能：在有序序列中找到第一个 严格大于 (>) 给定值的元素位置。
• 应用：upper_bound(a, right) 帮我们找到第一个“越出”右边界的位置。

3. 核心计算公式

两个迭代器相减，即是该数值在区间内出现的次数：

return ranges::upper_bound(a, right) - ranges::lower_bound(a, left);

三、 完整实现代码 (C++20 风格)

class RangeFreqQuery { // 哈希表：数值 -> 有序下标数组 unordered_map<int, vector<int>> pos; public: RangeFreqQuery(vector<int>& arr) { // 预处理：O(N) 建立索引 for (int i = 0; i < arr.size(); ++i) { pos[arr[i]].push_back(i); // 顺序遍历确保了下标序列是天然升序的 } } int query(int left, int right, int value) { // 使用定式查找，避免副作用 auto it = pos.find(value); if (it == pos.end()) return 0; // 数值根本没出现过 // 获取引用 (&)，拒绝大规模拷贝 const auto& a = it->second; // 二分查找：O(log M) auto L = std::ranges::lower_bound(a, left); auto R = std::ranges::upper_bound(a, right); return R - L; // 迭代器相减得到元素个数 } };

四、 总结

本题是典型的“空间换时间”策略。我们通过哈希表将乱序数组按值分类，再通过二分法将线性搜索优化为对数搜索。

关键点回顾：

1. 哈希表：掌握 find 定式，通过 Key 瞬间定位数据。
2. 引用 &：它是 C++ 程序员的性能尊严，拒绝无谓拷贝。
3. 二分边界：记住 lower 是第一个“不小于”，upper 是第一个“大于”。

相关链接：https://github.com/0voice