算法题：区间和的个数
def subarraySum(nums, target):
count = 0
for i in range(len(nums)):
total = 0
for j in range(i, len(nums)):
total += nums[j]
if total == target:
count += 1
return count
prefix_sum，并且之前已经出现过一个前缀和 prefix_sum - target，那么就说明存在一个子区间，其和等于目标值 target。通过这个技巧，我们可以将时间复杂度降到 O(N)。def subarraySum(nums, target):
prefix_sum = 0
count = 0
sum_dict = {0: 1} # 这个是为了处理边界情况，比如一个子数组的和刚好等于目标值
for num in nums:
prefix_sum += num
if prefix_sum - target in sum_dict:
count += sum_dict[prefix_sum - target]
if prefix_sum in sum_dict:
sum_dict[prefix_sum] += 1
else:
sum_dict[prefix_sum] = 1
return count
我们通过 prefix_sum变量来存储当前的前缀和。用一个哈希表 sum_dict来记录前缀和出现的次数。初始时，将sum_dict[0] = 1，这是为了处理一种特殊情况：如果一个子数组的和直接等于目标值，那么我们也能正确计算出来。遍历数组时，更新当前的 prefix_sum，然后检查prefix_sum - target是否已经在哈希表中出现过。如果出现过，说明从该位置到当前的子区间和为目标值。每遍历一个元素，就将当前的 prefix_sum存入哈希表中，记下它出现的次数。
对编程、职场感兴趣的同学，大家可以联系我微信：golang404，拉你进入“程序员交流群”。
虎哥作为一名老码农，整理了全网最全《python高级架构师资料合集》。
