LeetCode 523 连续的子数组和

题目

题解

如果事先计算出数组 nums 的前缀和数组，则对于任意一个子数组，都可以在 O(1) 的时间内得到其元素和。用 prefixSums[i] 表示数组 nums 从下标 00 到下标 i 的前缀和，则 nums 从下标 p+1 到下标 q（其中 p<q）的子数组的长度为 q−p，该子数组的元素和为 prefixSums[q]−prefixSums[p]。

如果 prefixSums[q]−prefixSums[p] 为 k 的倍数，且 q−p≥2，则上述子数组即满足大小至少为 2 且元素和为 k 的倍数。

当 prefixSums[q]−prefixSums[p] 为 k 的倍数时，prefixSums[p] 和 prefixSums[q] 除以 k 的余数相同。因此只需要计算每个下标对应的前缀和除以 k 的余数即可，使用哈希表存储每个余数第一次出现的下标。

var checkSubarraySum = function (nums, k) {
  const m = nums.length;
  if (m < 2) {
    return false;
  }
  const map = new Map();
  map.set(0, -1);
  let remainder = 0;
  for (let i = 0; i < m; i++) {
    remainder = (remainder + nums[i]) % k;
    if (map.has(remainder)) {
      const prevIndex = map.get(remainder);
      // 2 - 0 >= 2
      if (i - prevIndex >= 2) {
        return true;
      }
    } else {
      map.set(remainder, i);
      // 5 0
      // 1 2
    }
  }
  return false;
};

let nums = [23, 2, 4, 6, 7],
  k = 6;

console.log(checkSubarraySum(nums, k));

// 0 23%6
// 5
// 1 7%6
// 1
// 2 5%6
// 5
// 11%6
// 5
// 12%6
// 0

收获

我看到解题方法（上面的加粗划重点）我已经麻了，这是数学规律吗？

数组为 [23, 2, 4, 6, 7] k 为 6

prefixSums[q]−prefixSums[p] 为 k 的倍数

((23 + 2 + 4) - 23) % 6 = 0

只要下面这两个余数相同就可以了

23 % 6 = 5
(23 + 2 + 4) % 6 = 5