【中等】和可被K整除的子数组

  • Post author:
  • Post category:其他


在这里插入图片描述

刚开始用前缀和的方法试试,会超时

class Solution {
public:
    int subarraysDivByK(vector<int>& nums, int k) {
        int size = nums.size();
        vector<int> preSum(size + 1, 0);
        for (int i = 1; i <= size; i++)
            preSum[i] = preSum[i - 1] + nums[i - 1];
        int cnt = 0;
        for (int i = 1; i <= size; i++)
            for (int j = 0; j < i; j++)
                if ((preSum[i] - preSum[j]) % k == 0)
                    cnt++;
        return cnt;
    }
};

然后和

【中等】和为K的子数组

一样,也用散列表优化

class Solution {
private:
    map<int, int> mp;
public:
    int subarraysDivByK(vector<int>& nums, int k) {
       int sum = 0, cnt = 0;
       mp[0] = 1;
       for (int i = 0; i < nums.size(); i++)
       {
            sum += nums[i];
            int n = (sum % k + k) % k;
            //(sum % k + k) % k防止出现下标为负数的情况
            if (mp[n] > 0)
                cnt += mp[n];
            mp[n]++;
       }
       return cnt;
    }
};

用例子讲解一下我做这题的思路(思维比较发散,想到哪说到哪)


A = [4,5,0,-2,-3,1], K = 5


累加和对k求余,如果求到的余数出现过,那么一定可以在能求出这个余数的一个数或一串数后面找到和是k的倍数的子串。

比如[4, 1, 2, 2],和为9,对5求余得4,可以求出余数是4的数就是第一个4,而这个数后面一定能找到的和为5的子串[1, 2, 2]。(可以求出余数是4的要么是第一个数,要么是前面的一串数,所以得到和为5的子串一定会在第一个数或一串数后面,一定是连续的)

举个小例子细讲

a = [4, 5, 0] k = 5

第一个数得到余数4,mp[4] = 1。

然后4+5得9,9的余数是4,而mp[4]=1表明4出现过了,说明5一定可以被k整除,cnt += mp[4], 结果为1。

之后mp[4]会加1,原因是如果加上后面的数求余之后也是4,说明自己也能被k整除。但是别忘了,5能被k整除,自己也能被k整除,自然5和我加起来也能被k整除,所以加1是为了这个。

说来就来,0还正好能被5整除,所以此时cnt += mp[4]后cnt就是3了,包括了三种情况。

然后mp[4]会再再加1,原因再说一遍:如果加上0后面的数x后求余还是4,说明[5]、[0]、[x]、[5, 0]、[0, x]、[5, 0, x]都能被k整除,cnt加上mp[4]后就变成了6,包括了这6种情况



版权声明:本文为weixin_43318827原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。