Python中统计子序列和等于给定k的次数的代码优化方法

• 时间复杂度过高：两层循环本身已经是O(n²)复杂度，循环内每次调用sum(lista[i:j])需要再次遍历子数组，整体复杂度达到O(n³)，输入列表长度稍大就会触发超时。
• 逻辑冗余错误：elif somma < subtotal分支中重复累加子数组和的操作没有任何实际作用，额外浪费计算资源。
• 逻辑存在局限性：somma > subtotal就break的逻辑仅在数组全为正整数时生效，如果列表包含负数会直接导致统计结果错误。

你有C语言开发基础，可以把Python的字典理解为C语言中常用的哈希表KV存储，核心逻辑如下：

1. 定义前缀和pre_sum表示从列表开头遍历到当前位置的元素总和，那么区间[i,j)的连续子数组和等于pre_sum[j] - pre_sum[i]
2. 我们需要统计的就是满足pre_sum[j] - pre_sum[i] = subtotal的索引对(i,j)的数量，也就是对每个位置j，统计之前出现过多少次值为pre_sum[j] - subtotal的前缀和，将次数累加到结果中即可
3. 用字典存储「前缀和值: 该值出现的次数」，查询和插入的平均时间复杂度都是O(1)

def ex1(int_seq, subtotal):
    lista = convert(int_seq)
    cont = 0
    pre_sum = 0
    # 初始化字典：前缀和为0的情况默认出现1次，对应从列表开头到当前位置和刚好等于subtotal的场景
    sum_count = {0: 1}
    
    for num in lista:
        pre_sum += num
        target = pre_sum - subtotal
        # 累加符合要求的前缀和出现次数
        if target in sum_count:
            cont += sum_count[target]
        # 更新当前前缀和的计数
        sum_count[pre_sum] = sum_count.get(pre_sum, 0) + 1
    
    return cont

优化后仅需要遍历列表一次，整体时间复杂度降到O(n)，即使处理十万级以上的元素也不会超时，同时兼容列表包含正负数的所有场景，不会出现原代码的统计错误问题。

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