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

[zpc7]

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

参考题解: https://leetcode.cn/problems/subarray-sums-divisible-by-k/solution/you-jian-qian-zhui-he-na-jiu-zai-ci-dai-ni-da-tong/

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
function subarraysDivByK(nums, k) {

  let preSumModK = 0; // 前缀和模除

  let count = 0; // 将要返回的数目

  const map = { 0: 1 };

  for (let i = 0; i < nums.length; i++) {
    preSumModK = (preSumModK + nums[i]) % k; // 递推式子

    if (preSumModK < 0) {
      preSumModK += k;
    }


    if (map[preSumModK]) {      // 已经存在于map
      count = count + map[preSumModK]; // 把对应的次数累加给count(在这里处理count 说明 子数组和 是K的倍数, 那么必然存在能整除的子数组)
      map[preSumModK]++;        // 并且更新出现次数，次数+1
    } else {
      map[preSumModK] = 1;      // 之前没出现过，初始化值为1
    }
  }
  return count;
};