解决方案

方法一：前缀和与计数

思路

通常，涉及连续子数组问题的时候，我们使用前缀和来解决它们。我们令 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 意义下的值。如果说一共有 $$C_x$$ 个 $$P[i] \equiv x \pmod{K}$$ 。那么，就有 $$\sum_x \binom{C_x}{2}$$ 个可行的连续子数组。

举一个例子，给定数组为 A = [4,5,0,-2,-3,1]。那么 P = [0,4,9,9,7,4,5]，同时 $$C_0 = 2, C_2 = 1, C_4 = 4$$ ：

• 对于 $$C_0 = 2$$ （ $$P[0]$$ 、 $$P[6]$$ ），这表示一共有 $$\binom{2}{2} = 1$$ 的连续子数组的和能被 $$K$$ 整除，也就是 $$A[0:6] = [4, 5, 0, -2, -3, 1]$$ 。

• 对于 $$C_4 = 4$$ （ $$P[1]$$ 、 $$P[2]$$ 、 $$P[3]$$ 、 $$P[5]$$ ），这表示一共有 $$\binom{4}{2} = 6$$ 个连续子数组的和能被 $$K$$ 整除，分别是 $$A[1:2]$$ 、 $$A[1:3]$$ 、 $$A[1:5]$$ 、 $$A[2:3]$$ 、 $$A[2:5]$$ 、 $$A[3:5]$$ 。

复杂度分析

• 时间复杂度： $$O(N)$$ ，其中 $$N$$ 是数组 A 的长度。

• 空间复杂度： $$O(N)$$ 。（如果只存储 count 数组的话，那么解法的空间复杂度就可以变为 $$O(K)$$ 。）