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

链接：974.和可被K整除的子数组
难度：Medium
标签：数组、哈希表、前缀和
简介：给定一个整数数组 A，返回其中元素之和可被 K 整除的（连续、非空）子数组的数目。

题解 1 - typescript

• 编辑时间：2020-05-27
• 执行用时：96ms
• 内存消耗：39.7MB
• 编程语言：typescript
• 解法介绍：遍历一遍，O(n)，遍历到该值时累加，然后判断是否能够整除，若不能则判断所相差数，存入数组，若相差数在数组中不为 1 则累加数量，总思想：前面 i 和与前面 j 和余数相同，相减必可被整除。

var subarraysDivByK = function (A: number[], K: number): number {
  const arr: number[] = new Array(K).fill(0);
  let sum = 0;
  let count = 0;
  for (const num of A) {
    sum += num;
    if (sum % K === 0) count++;
    const y = (K - (sum % K)) % K;
    if (arr[y] !== 0) count += arr[y];
    arr[y] += 1;
  }
  return count;
};