关于mod的情况，有些时候可以直接考虑对0-k-1做处理。

题意

给定一个整数数组nums和一个整数k，返回总和能被k整除的非空子数组的数量。

一个子数组是一个数组的连续部分。

思路

这道题的基本思路就是首先计算前缀和，然后计算每一段是否可以整除k。这个算法是超时的。

func subarraysDivByK(nums []int, k int) int {
	length := len(nums)
	sum := make([]int, length)
	sum[0] = nums[0]
	pre := 0
	ans := 0
	for i := 0; i < length; i++ {
		if nums[i] % k == 0 {
			ans++
		}
		sum[i] = pre + nums[i]
		pre = sum[i]
	}

	// 1,2,3,4
	for l := 2; l <= length; l++ {
		pre := 0
		for start := l-1; start < length; start++ {
			diff := sum[start]-pre
			if diff % k == 0 {
				ans++
			}
			pre = sum[start+1-l]
		}
	}
	return ans
}

根据官方的解题思路，不是前缀和，利用前缀mod。

prefixSum[i] = A*k + R0

prefixSum[j] = B*k + R1

prefixSum[j] - prefixSum[i] = k(B-A) + (R1-R0) 如果要想[i, j]是一个答案，那就需要(R1-R0)%k = 0,

我们从索引0开始迭代所有的元素。我们为索引i处的每个元素设置**prefixMod = (prefixMod + num[i] % k + k) % k**，以找到从索引0到索引i的子阵列之和除以k后的余数。然后我们可以把之前看到的有相同余数的子数组的数量加起来，以抵消余数。这些数组的总数在modGroups[prefixMod]中。最后，我们将modGroups[R]的计数增加1，以包括当前有余数R的子数组，用于未来的匹配。

func subarraysDivByK(nums []int, k int) int {
	modK := make([]int, k)
	modK[0] = 1
	preMod, res := 0, 0
	for i := 0; i < len(nums); i++ {
		preMod = (preMod + nums[i]%k+k)%k
		res += modK[preMod]
		modK[preMod]++
	}
	return res
}