开发适配不同长度数组的子数组目标和计数算法

安全阿岳

2026-7-17

子数组和等于目标值的计数算法实现

暴力解法

暴力法思路直接，遍历所有可能的子数组并统计符合条件的数量：

外层循环确定子数组的起始索引
内层循环从起始索引开始累加元素，每完成一次累加就判断当前和是否等于目标值，符合则计数加1

Python实现代码：

def count_subarrays(nums, target):
    count = 0
    n = len(nums)
    for start in range(n):
        current_sum = 0
        for end in range(start, n):
            current_sum += nums[end]
            if current_sum == target:
                count += 1
    return count

复杂度分析：时间复杂度O(n²)，空间复杂度O(1)，适合数组长度较小的场景。

前缀和+哈希表优化解法

针对大规模数组，暴力法效率不足，前缀和结合哈希表的方法可将时间复杂度降至O(n)：
核心逻辑：假设prefix_sum[i]是数组前i个元素的和，那么子数组nums[j+1..i]的和等于prefix_sum[i] - prefix_sum[j]。若该差值等于目标值，说明此子数组符合要求。用哈希表记录每个前缀和的出现次数，遍历数组时，查询prefix_sum[i] - target的出现次数，即可得到以当前元素结尾的符合条件的子数组数量。

Python实现代码：

def count_subarrays(nums, target):
    count = 0
    prefix_sum = 0
    sum_freq = {0: 1}  # 初始前缀和0出现1次，处理从数组开头到当前元素和等于目标值的情况
    
    for num in nums:
        prefix_sum += num
        # 累加符合条件的子数组数量
        count += sum_freq.get(prefix_sum - target, 0)
        # 更新当前前缀和的出现次数
        sum_freq[prefix_sum] = sum_freq.get(prefix_sum, 0) + 1
    
    return count

复杂度分析：时间复杂度O(n)，空间复杂度O(n)，是处理大规模数组的最优方案。