974. 和可被 K 整除的子数组 前缀和+哈希表+同余定理_矩阵中和能被 k 整除的路径

974. 和可被 K 整除的子数组

难度：中等 2020/5/27每日一题打卡√
有一点不懂的是：明明哈希表来存取的时间复杂度和数组都是O(1)，但是在好多题里用数组比用哈希表速度快很多，就疑惑
题目描述

解题思路
一看到这种：大写加粗的 子数组 区间和 连续非空 就应该联想到前缀和
如果用暴力法时间复杂度O(n2)，才能求出每个区间的和。但是用前缀和能在O(n)内得到任意区间的和。这道题也一样，遍历一次数组，累加计算到当前数字的前缀和并且用哈希表保存已经出现过的前缀和以及次数。这道题跟经典的“和为K的子数组”不一样的是，要求和能整除K,稍微用特殊例子分析一下就可以知道，对每个前缀和对K取余存入哈希表，当两个位置的取余一样的时候，说明这个区间内子数组的和可以被K整除。
有个坑就是存在负数，在余数是负数的时候要把负数转换成正的

public int subarraysDivByK(int[] A, int K) {
			 HashMap<Integer, Integer> hashMap = new HashMap<>();
			 int sum = 0,count = 0;
			 hashMap.put(0, 1);  //初始化总和等于0
			 for (int i = 0; i < A.length; i++) {
				sum += A[i];
				int temp = (sum % K + K) % K;
				if(hashMap.containsKey(temp)) {  //如果取余之后下标相同，那么说明这段区间和能被整除
					int p =hashMap.get(temp);
					count += p;
					hashMap.put(temp, p+1);
				}else {
					hashMap.put(temp, 1);
				}
				//System.out.println(temp+" "+count+" "+hashMap.get(temp));
			}
			 return count;
		    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

时间24ms
哈希表在这道题里面也可以换成数组，因为余数范围肯定在[0，K-1]之间

public int subarraysDivByK(int[] A, int K) {
			 int mod[] = new int[K];
			 int sum = 0,count = 0;
			 mod[0] = 1;
			 for (int i = 0; i < A.length; i++) {
				sum += A[i];
				int temp = (sum % K + K) % K;
				if(mod[temp] != 0) {
					count += mod[temp];
				}
				mod[temp]++;
			}
			 return count;
		    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14