今日算法之_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));
}