You need to enable JavaScript to run this app. 如何设计优于O(n²)的算法统计数组中平均值为k的子数组数量
优惠活动
大模型
产品
解决方案
定价
更多

如何设计优于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的子数组总个数,此时前缀和+哈希表的优化思路完全适用。

算法实现逻辑

  1. 定义前缀和规则:prefix_sum[0] = 0,prefix_sum[m]表示数组b前m个元素的累加和
  2. 子数组b[i..j]的和等于prefix_sum[j+1] - prefix_sum[i],要这个值等于0,等价于prefix_sum[j+1] = prefix_sum[i]
  3. 遍历数组的过程中用哈希表记录每个前缀和出现的次数,每遇到重复的前缀和,就将对应出现次数累加到总结果中,同时更新哈希表的计数

复杂度说明

  • 时间复杂度: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:

  1. 转换后数组b为[-1, 1, 0, 2]
  2. 遍历得到的前缀和序列为0, -1, 0, 0, 2
  3. 统计得到符合要求的子数组共3个:[1,3]、[2]、[1,3,2],和代码运行结果一致

内容的提问来源于stack exchange,提问作者lyx

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.10.10 11:48:01