523.连续的子数组和

链接：523.连续的子数组和
难度：Medium
标签：数组、哈希表、数学、前缀和
简介：给你一个整数数组 nums 和一个整数 k。如果存在一个整数 n ，令整数 x 符合 x = n * k ，则称 x 是 k 的一个倍数。

题解 1 - typescript

• 编辑时间：2021-06-02
• 执行用时：156ms
• 内存消耗：53.9MB
• 编程语言：typescript
• 解法介绍：当 prefixSums[q]−prefixSums[p] 为 kk 的倍数时，prefixSums[p] 和 prefixSums[q] 除以 k 的余数相同。

function checkSubarraySum(nums: number[], k: number): boolean {
  const len = nums.length;
  if (len < 2 || k === 0) return false;
  const map = new Map<number, number>([[0, -1]]);
  let num = 0;
  for (let i = 0; i < len; i++) {
    num = (num + nums[i]) % k;
    let prev = map.get(num);
    if (prev !== undefined) {
      if (i - prev >= 2) return true;
    } else map.set(num, i);
  }
  return false;
}