leetcode974 和可被 K 整除的子数组
2020-03-25 本文已影响0人
奥利奥蘸墨水
题目
题目暴力解法
时间复杂度: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;
}
};