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的值组成一对。

然后这些次数里面,利用组合数公式C_{x}^{2}求出总的数目。

C_{x}^{2} = (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;
    }
};
上一篇下一篇

猜你喜欢

热点阅读