数组适合紧凑顺序存储，哈希结构用额外空间换取快速成员判断、频次统计和值到位置映射。

🧭 什么时候考虑这个专题

需要下标访问时先考虑数组；需要存在性、频次或映射时考虑哈希；连续区间和查询再考虑前缀和。

开始编码前先明确输入、输出、数据规模和允许修改的数据，再用一句话写出循环、窗口、堆或递归函数保持的不变量。

核心结构与复杂度

知识点核心规则常见复杂度
数组插入成本在数组中间插入元素通常需要搬移后续元素中间插入 O(n)
哈希查询复杂度合理哈希分布下查询平均为 O(1)平均 O(1)
可变哈希键键进入哈希表后不应修改参与哈希与相等比较的字段错误修改会导致查询失效
前缀和边界用长度 n+1 的前缀数组可统一表示闭区间和预处理 O(n)，查询 O(1)
频次表与集合只判断存在性用集合，需要保留次数时用值到计数的映射平均时间 O(n)

复杂度必须对应真实代码路径。哈希结构要区分平均与最坏情况，递归要计算调用栈，返回结果是否计入空间也应按题目口径说明。

适用边界

  • 数组插入成本： 末尾追加到动态数组通常是摊还 O(1)
  • 哈希查询复杂度： 最坏情况、碰撞和扩容成本不能省略
  • 可变哈希键： 修改无关字段不会改变桶定位
  • 前缀和边界： 区间 [left,right] 对应 prefix[right+1]-prefix[left]
  • 频次表与集合： 结果顺序与重复语义必须由题目契约决定

C# 实现检查

  1. 方法签名与题目契约一致，不依赖控制台输入输出。
  2. 数值计算检查 int 溢出，必要时先提升为 long。
  3. 集合选择说明平均复杂度、顺序语义和重复值处理。
  4. 字符串题明确使用 char、Rune、序号比较还是文化比较。
  5. 递归题说明终止条件、最大深度和退化输入。

⚠️ 常见误区

  • 数组插入成本： 不要把“数组支持 O(1) 随机访问，所以所有操作都是 O(1)”当成规则。
  • 哈希查询复杂度： 不要把“哈希查询在所有输入下都严格 O(1)”当成规则。
  • 可变哈希键： 不要把“哈希表会自动追踪键字段的变化”当成规则。
  • 前缀和边界： 不要把“前缀和能让预处理本身也变成 O(1)”当成规则。
  • 频次表与集合： 不要把“HashSet 能直接保留每个值的出现次数”当成规则。

练习顺序

先完成本组 5 道选择题，口述每个选项的边界；再独立实现编程题，最后对照参考答案检查不变量、复杂度和面试追问。