给定一串数nums和整数k，问这串数的子串和可以被k整除的子串（连续的一段）有多少
参考了Discussion：
先预处理prefix_sum（%k之后的值）
如果子串nums[i]~num[j]之和可以被k整除，说明prefix_sum[i] = prefix_sum[j]，于是用dict存各种prefix_sum的可能性有多少，最后
ans = sum(prefix_sum[x] * (prefix_sum[x]- 1) / 2), x=0~k-1
因为是C(n, 2)的组合数，所以不必等所有prefix_sum计算完再一个个算，在扫描nums，计算当前prefix_sum的时候顺便累加即可
注意初始化prefix_sum[0] = 1，因为一个数都不取的话和为0
1 #974
2 #Runtime: 232 ms (Beats 92.68%)
3 #Memory: 16.8 MB (Beats 37.80%)
4
5 class Solution(object):
6 def subarraysDivByK(self, nums, k):
7 """
8 :type nums: List[int]
9 :type k: int
10 :rtype: int
11 """
12 pre_sum = defaultdict(int)
13 t, ans = 0, 0
14 pre_sum[0] = 1
15 for i in nums:
16 t = (t + i) % k
17 pre_sum[t] += 1
18 ans += pre_sum[t] - 1
19 return ans