和可被 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]

分析：

如果sum1%k=n，sum2%k=n，那么(sum2-sum1)%k=0， 所以定义map，键对应了取模之后的结果，值对应了该结果出现的次数。 如果map中已经存在该结果则更新它的value，如果不存在则添加并置value=1。 当取模之后的结果为负数时要加k。

public int subarraysDivByK(int[] a, int k) { if(a.length==0) return 0; Map<Integer,Integer> map=new HashMap<>(); int count=0; int sum=0; map.put(0,1); for(int i=0;i<a.length;i++) { sum+=a[i]; int mod=sum%k; if(mod<0) mod+=k;//!!! if(map.containsKey(mod)) { count+=map.get(mod); map.put(mod, map.get(mod)+1); }else { map.put(mod,1); } } return count; }