Java：如何在给定起止索引区间内O(1)查询字符出现次数

预处理步骤 #

• 针对目标字符串，为每个出现过的字符构建前缀和数组：
  • 假设字符串长度为n，对字符c，前缀和数组prefix[c]的长度为n+1
  • prefix[c][0] = 0（表示前0个字符中c出现0次）
  • 遍历字符串的每个索引i（从0到n-1），prefix[c][i+1] = prefix[c][i] + (1 if 当前字符等于c else 0)
• 实现时可以用哈希表（比如Python的dict）存储每个字符对应的前缀和数组，只保留字符串中实际出现过的字符，节省空间。预处理整体时间复杂度为O(n)，因为每个字符的遍历是线性的，且字符种类是常数级（比如ASCII字符固定256种）。

O(1)查询步骤 #

对于任意查询的区间[start, end]（闭区间，索引从0开始）和目标字符c：

1. 先确认字符c的前缀和数组存在（若不存在，直接返回0）
2. 计算区间内c的出现次数：count = prefix[c][end + 1] - prefix[c][start]

示例验证（以字符串stackoverflow为例） #

字符串索引对应：0:s,1:t,2:a,3:c,4:k,5:o,6:v,7:e,8:r,9:f,10:l,11:o,12:w

• 字符o的前缀和数组为：[0,0,0,0,0,0,1,1,1,1,1,1,2,2]
• 查询索引1-6区间的o次数：prefix['o'][7] - prefix['o'][1] = 1 - 0 = 1
• 查询索引7-12区间的o次数：prefix['o'][13] - prefix['o'][7] = 2 - 1 = 1
• 查询索引0-12区间的o次数：prefix['o'][13] - prefix['o'][0] = 2 - 0 = 2
  完全符合示例结果。

内容的提问来源于stack exchange，提问作者Alice