解决方案
方法一:前缀和与计数
思路
通常,涉及连续子数组问题的时候,我们使用前缀和来解决它们。我们令 P[i+1] = A[0] + A[1] + ... + A[i]
。那么,每个连续子数组就可以写成 P[j] - P[i]
(其中 j > i
) 的形式。因此,我们将 P[j] - P[i]
模 K
等于 0
等价于 P[i]
与 P[j]
在模 K
的意义下同余。
算法
计算所有的 P[i]
在模 K
意义下的值。如果说一共有 个 。那么,就有 个可行的连续子数组。
举一个例子,给定数组为 A = [4,5,0,-2,-3,1]
。那么 P = [0,4,9,9,7,4,5]
,同时 :
-
对于 (、),这表示一共有 的连续子数组的和能被 整除,也就是 。
-
对于 (、、、),这表示一共有 个连续子数组的和能被 整除,分别是 、、、、、。
复杂度分析
-
时间复杂度:,其中 是数组
A
的长度。 -
空间复杂度:。(如果只存储
count
数组的话,那么解法的空间复杂度就可以变为 。)