如何设计优于O(n²)的算法统计数组中平均值为k的子数组数量
平均值等于k的子数组计数算法实现
问题等价转换
你认为前缀和+哈希表思路不适用是因为没有做条件变形,我们可以先对问题做等价转换:
假设子数组范围为下标i到j(闭区间,长度为j-i+1),平均值等于k的条件为:
(a[i] + a[i+1] + ... + a[j])/(j-i+1) = k
两边乘以长度变形后可得:
(a[i]-k) + (a[i+1]-k) + ... + (a[j]-k) = 0
也就是说只要把原数组的每个元素都减去k得到新数组b,原问题就等价为统计数组b中和为0的子数组总个数,此时前缀和+哈希表的优化思路完全适用。
算法实现逻辑
- 定义前缀和规则:
prefix_sum[0] = 0,prefix_sum[m]表示数组b前m个元素的累加和 - 子数组b[i..j]的和等于
prefix_sum[j+1] - prefix_sum[i],要这个值等于0,等价于prefix_sum[j+1] = prefix_sum[i] - 遍历数组的过程中用哈希表记录每个前缀和出现的次数,每遇到重复的前缀和,就将对应出现次数累加到总结果中,同时更新哈希表的计数
复杂度说明
- 时间复杂度:O(n),仅需要遍历数组1次,哈希表的插入、查询均为均摊O(1)操作
- 空间复杂度:O(n),最坏情况下所有前缀和都不重复,哈希表需要存储n+1个键值对
代码示例(Python)
def count_target_avg_subarrays(a, k): total = 0 current_prefix = 0 # 哈希表初始记录前缀和0出现1次 sum_counter = {0: 1} for num in a: current_prefix += (num - k) if current_prefix in sum_counter: total += sum_counter[current_prefix] sum_counter[current_prefix] += 1 else: sum_counter[current_prefix] = 1 return total
验证示例
输入数组a = [1,3,2,4],k=2:
- 转换后数组b为
[-1, 1, 0, 2] - 遍历得到的前缀和序列为
0, -1, 0, 0, 2 - 统计得到符合要求的子数组共3个:
[1,3]、[2]、[1,3,2],和代码运行结果一致
内容的提问来源于stack exchange,提问作者lyx
相关产品推荐
相关产品推荐

