【前缀和】974. 和可被 K 整除的子数组

**前缀和**

前缀和是一种常见的算法技巧，用于解决涉及累加或求和的问题。它通过预先计算每个位置的总和来实现，这样就可以在 O(1) 的时间复杂度内求出任意子数组的和。

**问题描述**

给定一个整数数组 `nums` 和一个正整数 `k`，要求找出所有和可被 `k` 整除的子数组的数量。

**解决方案**

我们可以使用前缀和来解决这个问题。首先，我们计算每个位置的前缀和，然后遍历数组，检查每个子数组的和是否能被 `k` 整除。如果能，则加1 到答案中。

def subarraySum(nums, k):
 n = len(nums)
 # 计算前缀和 prefix_sum = [0] * (n +1)
 for i in range(n):
 prefix_sum[i +1] = prefix_sum[i] + nums[i]
 count =0 # 遍历数组，检查每个子数组的和是否能被 k 整除 for i in range(n +1):
 for j in range(i, n +1):
 if (prefix_sum[j] - prefix_sum[i]) % k ==0:
 count +=1 return count

nums = [1,2,3]
k =3print(subarraySum(nums, k)) # Output:3nums = [4,5,0,9,6]
k =6print(subarraySum(nums, k)) # Output:4

if k ==0:
 return0elif k < 0:
 k = -k