前缀和-974.和可被k整除的子数组-力扣(LeetCode)

一、题目解析

1、子数组是数组中连续的部分

2、nums[-10^4，10^4]，不能用滑动窗口优化

二、算法原理

解法1：暴力解法-枚举 O(N^2)

对于解法2的补充知识

1、同余定理

(a-b)/p=k……0->a%p=b%p

举例9%2=1，(2*4+1)%2=1%2，结合这个我们可以证明同余定理

证明：

(a-b)/p=k->a=b+p.k，对两边同时取余数，a%p=(b+p.k)%p=b%p

证毕

2、c++，java：[负数%正数]的结果以及修正

这里我们直接记结论，负数%正数=负数，-a%p=-a，对其进行修正，-a%p+p，最后在模上p，(-a%p+p)%p

解法2：前缀和+哈希表

我们需要找以最后位置为结尾的所有子数组，结合我们补充的知识，我们可以将问题转化

将问题转化为在[0，i-1]区间内找前缀和余数等于(sum%k+k)%k，对于哈希表unordered_map<int,int> hash，第一个int是前缀和余数，第二个int为出现的频率

细节问题：

1、前缀和插入数组的时机？

 在判断完前缀和余数是否存在后，加入前缀和余数

2、由于前缀和余数会存进哈希表中，所以可以用一个变量记录新计算的前缀和余数，没必要开一个前缀和余数数组

3、如果整个前缀和所得余数为k，则hash[0]=1

4、什么时候统计子数组数目？

通过hash.count((sum%k+k)%k)，如果哈希表中存在该余数，则该余数的频率可以加入到最终结果中

三、代码示例

解法2：

class Solution {
public:
    int subarraysDivByK(vector<int>& nums, int k)
    {
        int sum = 0,ret = 0;
        unordered_map<int,int> hash;
        hash[0] = 1;
        for(auto& e : nums)
        {
            sum += e;
            if(hash.count((sum%k+k)%k))
            {
                ret += hash[(sum%k+k)%k];
            }

            hash[(sum%k+k)%k]++;
        }
        return ret;
    }
};

看到最后，如果对您有所帮助，还请点赞、收藏和关注，我们下期再见！