LeetCode每日一题5月27日 LeetCode974. 可被K整除的子数组

待我称王封你为后i 2023-02-13 03:41 41阅读 0赞

## 问题描述： ##

给定一个整数数组 `A`，返回其中元素之和可被 `K` 整除的（连续、非空）子数组的数目。

来源：力扣（LeetCode）  
链接：[https://leetcode-cn.com/problems/subarray-sums-divisible-by-k][https_leetcode-cn.com_problems_subarray-sums-divisible-by-k]

**示例：**

输入：A = [4,5,0,-2,-3,1], K = 5
    输出：7
    解释：
    有 7 个子数组满足其元素之和可被 K = 5 整除：
    [4, 5, 0, -2, -3, 1], [5], [5, 0], [5, 0, -2, -3], [0], [0, -2, -3], [-2, -3]
    
    
    提示：
    
    1 <= A.length <= 30000
    -10000 <= A[i] <= 10000
    2 <= K <= 10000

## 解题思路： ##

暴力解法，双层循环，

**第一层循环计算 A\[0\]-A\[i-1\]的值，i<=A.size();**

**    第二层循环计算A\[0\]-A\[j-1\]的值，j<i**

**完成代码如下：**

class Solution {
    public:
        int subarraysDivByK(vector<int>& A, int K) {
            int res = 0;
            int sum = 0;
            for(int i=0;i<A.size();i++){
                sum+=A[i];
                if(sum%K==0) res++;
                int tempsum = sum;
                for(int j=0;j<i;j++){
                    tempsum -= A[j];
                    if(tempsum%K==0) res++;
                }
            }
            return res;
        }
    };

但是这个解法有个测试用例超出了运行时间

所以我们需要进行一些优化，优化思路借助评论区大神和[LeetCode560，和为k的子数组][LeetCode560_k]

运用前缀和的思想。

我们首先要知道一个原理，就是在原数组上面任何位置任何数加上`n*K`(n是整数)，对结果不会产生影响

即和为元素 a 和 a+n\*k俩种情况是等价的。

class Solution {
    public:
        int subarraysDivByK(vector<int>& A, int K) {
            int res = 0;
            int sum = 0;
            map<int,int> m;
            m[0]=1;
            for(int i=0;i<A.size();i++){
                /*比如说K=5,当前的的sum=4,那么4可以和之前出现的-1组合，也是5的倍数。-1取余还是-1，
                是（-1+5)取余是4，4和4也可以组合，不影响计算结果。当然也可以不纠正成正数，
                保留(-K,K)的范围，计算的时候算两个，4需要统计4、-1的结果*/
                if(A[i]<0) A[i]=(A[i]%K)+K;
                sum += A[i];
                res += m[sum%K];
                m[sum%K]++;
            }
            return res;
        }
    };

[https_leetcode-cn.com_problems_subarray-sums-divisible-by-k]: https://leetcode-cn.com/problems/subarray-sums-divisible-by-k
[LeetCode560_k]: https://leetcode-cn.com/problems/subarray-sum-equals-k/