题目
题目
暴力解法
时间复杂度：O(n^3)
空间复杂度：O(1)
两遍for循环，对i, j间的数求和。然后判断能不能被k整除。
优化的暴力（利用前缀和）
时间复杂度：O(n^2)
空间复杂度：O(n)
思路跟前面的暴力是一样的，只是利用前缀和数组将，求和的过程优化为O(1)的时间复杂度。
前缀和 + 同余定理
同余定理：给定一个正整数m，如果两个整数a和b满足a-b能够被m整除，即(a-b)/m得到一个整数，那么就称整数a与b对模m同余，记作a≡b(mod m)。对模m同余是整数的一个等价关系。
再上一个解法中用到的前缀和，要求i,j之间的和，我们可以利用sum(j) - sum(i - 1)。然后判断这个差值能不能被k整除，即mod k等于0。
根据同余性质，可以得到：sum(j) % k == sum(i - 1) % k
即是说，如果前j项的和，如果和前i（i < j）的和相等，那么那么他们i到j之间的数的和，就能被k整除。
任何数mod k的值都会落在0到k-1之间，所以我们可以开一个大小为k的数组，来保存落在前缀和取模落在的位置上数目x。这x中任意两个都能让他们之间的数的和能被k整除。
有一个例外，那就是前缀和取模结果为0的时候，那么它不需要跟任何其他的数配对，它自己就能使0到它本身的位置的和能被k整除。当然它也能和另一个取模为0的值组成一对。
然后这些次数里面，利用组合数公式求出总的数目。
= (x - 1) * x / 2 = 1 + 2 + .. + (x - 1)
所以我们不必等他所有值统计完了再用组合数公式来计算。可以提前相加。
代码
class Solution {
public:
int subarraysDivByK(vector<int>& nums, int k) {
int res = 0, sum = 0;
int len = nums.size();
vector<int> vec(k, 0);
vec[0] = 1; //mode 的结果为0时，不需要跟别的结果配对。
for (int i = 0; i < len; i++){
sum += nums[i];
int key = (sum % k + k) % k; //防止sum模k的结果为负数所以给他加k再模一次k
res += vec[key];
vec[key]++;
}
return res;
}
};
