力扣Leetcode第974题:和可被K整除的子数组（前缀和）

冷不防 2023-02-13 05:40 4阅读 0赞

题目描述：

> 给定一个整数数组 A，返回其中元素之和可被 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

这个题目说白了也是一个从所有子数组里挑选满足条件的。和560题和为k的子数组是一样的，但是这道题的数组元素数量比那道题多一些。  
了解前缀和，可以先去看看上一道题目：  
[leetcode560题:和为k的子数组][leetcode560_k]

### 一.暴力法 ###

从示例给出的解释，可以看到，这种最容易想到的办法就是暴力查找组合，然后依次判断。

从任何一个位置开始，往后加剩下的元素，如果加了之后可以整除就给 count++，否则count不++，只往后加剩下的元素。

class Solution {
        
        public int subarraysDivByK(int[] A, int K) {
        
            int count=0;
            for(int i=0;i<A.length;i++){
        
                if(A[i]%K==0){
        
                    count++;
                }
                for(int j=i+1;j<A.length;j++){
        
                    A[i]+=A[j];
                    if(A[i]%K==0){
        
                        count++;
                    }
                }
            }
            return count;
        }
    }

和560题一样的暴力做法,超时了.

因此根据上一个题的做法，很容易想到前缀和，那么直接计算前缀和，再进行遍历显然也是不行的，因为时间会比暴力法更长。

### 二.前缀和+哈希表优化 ###

上一道题的主要点在于：和为K。

对于一个位置 i 和另一个位置 j 来说，前缀和 preSum\[j\] - preSum\[i\]=k ，移项得到 pre Sum\[j\] - k= preSum\[i\] ，在map 里找 preSum\[i\] 的 value 就能够用来判断从 i 到 j 这段子数组是否满足条件。

然鹅对于这道题，应该满足的是 **(preSum\[j\]-preSum\[i\])%K=0** 这个等式，拆分一下，也就是 **preSum\[j\]%K=preSum\[i\]%K.**

然而两个前缀和模K之后的值相等，对应本身不一定相等，所以map里存储的话，没法统计了。  
怎么办？  
干脆在preSum数组里，就存储模 K 之后的值，这样并不影响结果。  
另外，因为这道题会有负数，因此需要稍做处理。

其余的做法就和之前和为 K 的数组做法一样了。

class Solution{
        
        public int (int[] A, int K){
        
            int count=0;
            int preSum=0;
            Map<Integer,Integer> map=new HashMap<>();
            map.put(0,1);
            for(int a: A){
        
                preSUm+=a;//同时计算前缀和
    
                int currMo=(preSum%K+K)%K;//处理负数
                int preMoCount=map.getOrDefault(curMo,0);//获取符合条件的key对应的value值
                
                count+=preMoCount;//更新结果
                map.put(currMo,preMoCount+1);
            }
            return count;
        }
    }

### 三.前缀和+哈希表优化 ( 2 ) ###

上面我们是在一边计算前缀和模 k 之后的值，一边在 map 里面查找对应的 value 并且进行累加，这个方法在之前的560题里也提到了.但是对于这一题，我们还可以换一个做法。

我们直接从最终的 map 入手,里面的每一个键值对都计算 value\*(value-1)/2 的值并累加.

为什么这么算呢，上面的等式**preSum\[j\]%K=preSum\[i\]%K.**  
试想这样的一个原数组:

**xxxxx i xxxxxx j xxxx**

i 位置的前缀和模 k 的值, 和 j 位置的前缀和模 k 的值是一样的,那么他们之间的这段,显然多出来的就是整数倍的 k .所以组合数就是1;

那如果三个位置呢(对应的 map 里有一个 key 对应的 value 是 3 ) ,  
就代表有三个位置对应的前缀和模 k 后的值相等，组合出的子数组数量就是 1+1+1=3.  
也就是这个公式 value\*(value-1)/2 进行计算.

**再转义一下这个思路:n 位置的前缀和都满足模 K后的值相等的条件，那么他们之间任意组合的子数组一定是 K 的倍数。**

（显然，这种方法在那个560题，和为K的子数组里并不适用，  
如果还是用**xxxxx i xxxxxx j xxxx**这个数组,在map里 i 位置和 j 位置的前缀和一样,所以对应同一个key ,value 是2. 这只能说明 i 和 j 这段子数组和为 0,我们要的结果是和为 k , 所以没法用这两个子数组进行组合.  
这一道题是求模 , 运算本身具有特殊性质，和那个求和的不要搞混就ｏｋ，本人在这块把两个题在一起对比，越想越迷糊．．．)

代码如下：

class Solution {
        
        public int subarraysDivByK(int[] A, int K) {
        
            Map<Integer, Integer> map= new HashMap<>();
            map.put(0, 1);
            int sum = 0;
            for (int a: A) {
        
                sum += a;
                //当被除数为负数时取模结果为负数，需要纠正
                int currMo = (sum % K + K) % K;
                map.put(currMo, map.getOrDefault(currMo, 0) + 1);
            }
    
            int count = 0;
            for (Map.Entry<Integer, Integer> entry: map.entrySet()) {
        
                //直接使用这个公式,那些只出现一次的,也就是模k不为0的结果都会在-1计算后变成0
                //所以参与累加的部分其实只是那个key=0的键值对
                count += entry.getValue() * (entry.getValue() - 1) / 2;
            }
            return count;
        }
    }

[leetcode560_k]: https://blog.csdn.net/weixin_42092787/article/details/106378323