寻求基于哈希的整数数组‘好区间’计数O(nlogn)算法

问题定义 #

“好区间”指连续子数组中每个整数的出现次数均为偶数（含0次）。需统计这类区间的总数，且要求时间复杂度优于O(n²)，目标为O(nlogn)。

核心思路：前缀状态掩码 + 平衡树计数 #

利用奇偶性的异或特性：一个数出现偶数次等价于其奇偶状态（奇/偶）变化次数为偶数，可通过二进制掩码记录前缀的奇偶状态，再统计相同掩码的出现次数来计算符合条件的区间数。

具体步骤 #

1. 映射整数到二进制位

   • 遍历数组，用哈希表给每个唯一整数分配一个唯一的二进制位（例如：第一个新数对应第0位，第二个对应第1位，依此类推）。这一步确保每个数的出现次数奇偶性可通过掩码的某一位来表示：1代表奇数次，0代表偶数次。

2. 前缀掩码遍历与计数

   • 初始化：前缀掩码mask = 0（对应空前缀，所有数出现次数为0，均为偶数）；用平衡树维护各掩码的出现次数，初始时count_map[0] = 1。
   • 遍历数组每个元素：
     • 更新掩码：mask ^= (1 << bit_pos[当前元素])（异或操作翻转该数对应的奇偶位）。
     • 若count_map中已存在当前mask，则将其出现次数累加至结果（每一对相同掩码的前缀，对应中间的子数组是好区间）。
     • 更新count_map：将当前mask的计数加1（若不存在则设为1）。

3. 结果计算
   最终累加的数值即为所有好区间的数量。

示例验证 #

示例1：数组[7,7,1,5,5,1] #

• 映射：7→bit0，1→bit1，5→bit2
• 前缀掩码序列：000→001→000→010→110→010→000
• 掩码出现次数：000(3次)、001(1次)、010(2次)、110(1次)
• 结果：组合数C(3,2) + C(2,2) = 3 + 1 = 4，与示例一致。

示例2：数组[4,5,6,5,4] #

• 映射：4→bit0，5→bit1，6→bit2
• 前缀掩码序列：000→001→011→111→101→100
• 所有掩码唯一，组合数为0，与示例一致。

复杂度分析 #

• 映射整数到二进制位：O(n)
• 遍历数组并更新掩码：O(n)
• 平衡树的插入/查询操作：每次O(logk)（k为不同掩码的数量，最大为n+1）
• 总时间复杂度：O(nlogn)，满足要求。

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