今日算法之_79_和可被K整除的连续子数组
前言
Github：https://github.com/HealerJean
1、和可被K整除的连续子数组
给定一个整数数组 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.1、解题思路
sum1%k=n，sum2%k=n，那么(sum2-sum1)%k=0
用sum保存前n个数之和，计算每个sum的余数，保存。余数相同则可以整除 ， 如
A = [4,5,0,-2,-3,1], K = 5
p[0] = 4, p[1] = 9, p[2] = 9, p[3] = 7, p[4] = 4, p[5] = 5
余数对应 4，4，4，2，4，0;
余数 4 有 4 个，排列组合法，排列组合，从同余里取2个数，除去有序情况，(4 * 3) / (2 * 1) ，结果为6
余数 2 有 1 个，排列组合结果为0，
余数 0 有1个，排列组合结果为1 ， 表示当前到达的位置本身就能整除。相当于有几个 0， 集合就多几个。
假如有n个0，那么最终的结果是 n + (n * ( n - 1 ) / 2) = ( n + 1 ) n / 2 ，所以我们下面的算法可以选择提前放入一个
最终答案为7
针对sum为负数取余为的情况，sum为负数，取余数，也是负数。这就增加了一点点难度。
比如 （-1, 2, 9）k = 2 ，sum取余依次是-1，1，0。如果按照上面的逻辑很明显只有1种情况出现，也就是（-1,2,9），而 ( 2 ) 这种呢情况没有出现，就是因为前一个数是负数的原因，所以我们要想办法让它变成正数 。如下，这样的话，sum取余依次是 1,1,0 。这样就有2种情况了
//当被除数为负数时取模结果为负数，需要纠正
// 这个地方非常巧妙， 比如如果是 -1%5 余数为-1 。 如果是-4%5 余数为 -4 。但是这里都是负数，不好参与
// （正数 + k）% k 不会影响值
// （负数 + k）$ k 会是一个正数(找到最接近0的正数)。
// [-1,2,9] 2 => 如果是 正常的sum%k的情况，那么本来2就是一个结果集，但是缺由于余数为-1会有问题
int mod = (sum % K + K) % K;
1.2、算法
public int subarraysDivByK(int[] A, int K) {
Map<Integer,Integer> map = new HashMap();
// 余数为0，表示当前到达的位置本身就能整除。（相当于有几个 0， 集合就多几个。加入有n个0，那么最终的结果是 n + n(-1)/2 = n(n+1)/2 ，所以我们提前放入一个
map.put(0,1);
int sum = 0;
for(int num : A){
sum += num;
//当被除数为负数时取模结果为负数，需要纠正
// 这个地方非常巧妙， 比如如果是 -1%5 余数为-1 。 如果是-4%5 余数为 -4 。但是这里都是负数，不好参与
// （正数 + k）% k 不会影响值
// （负数 + k）$ k 会是一个正数(找到最接近0的正数)。
// 错误，[-1,2,9] 2 => 如果是 正常的sum%k的情况，那么本来2就是一个结果集，但是缺由于余数为-1会有问题
// 正确，（-1, 1, 4）比如 -1的结果是4， 将来在4的时候，结果还是4，这样 （1,4）就成为了一组
int mod = (sum % K + K) % K;
map.put(mod, map.getOrDefault(mod,0) + 1);
}
int count = 0;
for(int num : map.keySet()){
// 排列组合，从同余里取2个数，除去有序情况
count += map.get(num) * (map.get(num)-1) / 2;
}
return count;
}
1.3、测试
@Test
public void test(){
int[] A = {4,5,0,-2,-3,1} ;
int K = 5 ;
System.out.println(-6%5); //= -1
System.out.println(subarraysDivByK(A, K));
}
