求解最多含k个奇数的不同连续子数组数量的O(nlogn)算法
问题描述
给定整数数组nums，统计其中最多包含k个奇数的不同连续子数组总个数：两个子数组只要存在任意一个位置的元素不同，即判定为不同子数组。
现有实现仅能达到O(n²)时间复杂度，以下提供O(nlogn)时间复杂度的优化方案。
测试用例
- 用例1
输入：
nums = [3, 2, 3, 4], k = 1
输出：7
解释：符合要求的子数组包括[3], [2], [4], [3, 2], [2, 3], [3, 4], [2, 3, 4]，[3, 2, 3]包含2个奇数超过限制，不计入结果。
- 用例2
输入：
nums = [1, 3, 9, 5], k = 2
输出：7
解释：符合要求的子数组包括[1], [3], [9], [5], [1, 3], [3, 9], [9, 5]。
- 用例3
输入：
nums = [3, 2, 3, 2], k = 1
输出：5
解释：符合要求的子数组包括[3], [2], [3, 2], [2, 3], [2, 3, 2]，重复子数组不重复计数，奇数数量超过k的子数组不计入。
- 用例4
输入：
nums = [2, 2, 5, 6, 9, 2, 11, 9, 2, 11, 12], k = 1
输出：18
O(nlogn)优化思路
我们需要同时满足两个约束：子数组奇数数量≤k、子数组内容去重，拆分处理如下：
1. 预处理奇数数量约束
首先构建奇数前缀和数组prefix_odd，其中prefix_odd[i]表示数组前i个元素（下标0到i-1）中的奇数总个数。
任意子数组[l, r]（下标从l到r）的奇数数量为prefix_odd[r+1] - prefix_odd[l]，对于每个右边界r，我们可以通过二分查找找到最小的左边界left_min，满足prefix_odd[r+1] - prefix_odd[left_min] ≤k，所有l ∈ [left_min, r]对应的子数组[l, r]都符合奇数数量要求，这一步的时间复杂度为O(nlogn)。
2. 不同子数组去重
要在O(nlogn)时间内完成去重，推荐使用后缀数组方案：
- 先构建整个数组的后缀数组，将所有后缀按字典序排序，时间复杂度O(nlogn)。
- 计算高度数组
height，其中height[i]表示排序后第i个后缀和第i-1个后缀的最长公共前缀长度，时间复杂度O(n)。 - 对于每个下标为i的后缀，我们先预处理得到最大可扩展长度
max_len：即从i开始最长的连续子数组，满足其中奇数数量≤k，可通过前缀和数组二分查找得到。 - 遍历排序后的所有后缀，每个后缀贡献的新增不同子数组数量为
max(0, max_len - height[i])，累加所有贡献即可得到最终结果。
该方案整体时间复杂度为O(nlogn)，且不存在最坏情况退化到O(n²)的问题。
简化实现（适合小规模数据）
如果数据量不大，也可以使用滚动哈希（Rabin-Karp）方案实现，代码编写更简单：
from bisect import bisect_left def count_distinct_subarrays(nums, k): n = len(nums) # 预处理奇数前缀和 prefix_odd = [0] * (n + 1) for i in range(n): prefix_odd[i+1] = prefix_odd[i] + (nums[i] % 2) # 预计算滚动哈希参数 base = 911382629 mod = 10 ** 18 + 3 prefix_hash = [0] * (n + 1) power = [1] * (n + 1) for i in range(n): prefix_hash[i+1] = (prefix_hash[i] * base + nums[i]) % mod power[i+1] = (power[i] * base) % mod hash_set = set() for r in range(n): target = prefix_odd[r+1] - k left_min = bisect_left(prefix_odd, target, 0, r + 1) # 统计所有合法子数组的哈希 for l in range(left_min, r + 1): sub_len = r - l + 1 sub_hash = (prefix_hash[r+1] - prefix_hash[l] * power[sub_len]) % mod hash_set.add(sub_hash) return len(hash_set)
如果担心哈希冲突，可以使用双哈希（两套不同的base和mod）进一步降低冲突概率。
内容的提问来源于stack exchange，提问作者Prachi Palod
