leetcode974

这道题目描述很清晰，直接两层循环，代码如下：

 1 class Solution(object):
 2     def subarraysDivByK(self, A: 'List[int]', K: int) -> int:
 3         n = len(A)
 4         totalnum = 0
 5         for i in range(n):
 6             cursum = 0
 7             for j in range(i,n):
 8                 cursum += A[j]
 9                 if cursum % K == 0:
10                     totalnum += 1
11 
12         return totalnum

显然，时间复杂度O(n^2)，这样会超时。

因此需要优化，把时间复杂度减少O(n)，一般这种类型的题目，都是要从数学角度分析，寻找规律。

先贴代码：

 1 class Solution(object):
 2     def subarraysDivByK(self, A: 'List[int]', K: int) -> int:
 3         n = len(A)
 4         totalnum = 0
 5         preDic = dict()
 6         cursum = 0
 7         for i in range(n):
 8             cur = A[i]
 9             cursum += cur
10             res = cursum % K
11             if res == 0:
12                 totalnum += 1
13             if res in preDic:
14                 totalnum += preDic[res]
15                 preDic[res] += 1
16             else:
17                 preDic[res] = 1
18         return totalnum

这里比较关键的代码就是13～17行，对于前m项的连加和，模K的余数，如果是第一次出现，则在字典中进行“标记”。

如果不是第一次出现，则执行第14行代码，这看起来很奇怪。

那就使用实际的示例，调试代码来分析，测试用例是[4,5,0,-2,-3,1]，K值为5。

当i==0时，A[i]的值是4，(res==4)因此preDic中增加{4:1}这一项，

当i==1时，A[i]的值是5，(res==4)这说明从上一次出现res==4，到本次出现res==4之间的区间，可能出现了0到x个K，x的值是多少呢？

恰好就是preDic[res]的值！

假设preDic[4] = 2，那么2这个值一般解读为：“余数为4的次数”。

也可以解读为：“到目前为止，已经出现了几次K的倍数，并且余数为4”。而这个次数，是等于数值-1。

即preDic[4] == 1时，表示第一次出现余数4，那么之前就有0次K的倍数。

predDic[4] == 2时，表示第二次出现余数4，那么之前就有1次K的倍数。因此才会有第14行：totalnum += preDic[res]。