0523. 连续的子数组和【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 前缀和 + 哈希表
• 3. 🔗 引用

1. 📝 题目描述

• leetcode

给你一个整数数组 nums 和一个整数 k，如果 nums 有一个好的子数组返回 true，否则返回 false：

一个好的子数组是：

• 长度至少为 2，且
• 子数组元素总和为 k 的倍数。

注意：

• 子数组是数组中连续的部分。
• 如果存在一个整数 n，令整数 x 符合 x = n * k，则称 x 是 k 的一个倍数。0 始终 视为 k 的一个倍数。

---

示例 1：

输入：nums = [23,2,4,6,7], k = 6
输出：true
解释：[2,4] 是一个大小为 2 的子数组，并且和为 6。

示例 2：

输入：nums = [23,2,6,4,7], k = 6
输出：true
解释：[23, 2, 6, 4, 7] 是大小为 5 的子数组，并且和为 42。
42 是 6 的倍数，因为 42 = 7 * 6 且 7 是一个整数。

示例 3：

输入：nums = [23,2,6,4,7], k = 13
输出：false

---

提示：

• 1 <= nums.length <= 10^5
• 0 <= nums[i] <= 10^9
• 0 <= sum(nums[i]) <= 2^31 - 1
• 1 <= k <= 2^31 - 1

2. 🎯 s.1 - 前缀和 + 哈希表

js

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {boolean}
 */
var checkSubarraySum = function (nums, k) {
  const n = nums.length
  if (n < 2) return false

  const map = new Map()
  // 初始化，前缀和余数为 0 的下标为 -1，为了处理从下标 0 开始的子数组
  map.set(0, -1)

  let prefixSum = 0

  for (let i = 0; i < n; i++) {
    prefixSum += nums[i]

    // 计算余数，同余定理：
    // (sum[i] - sum[j]) % k == 0  =>  sum[i] % k == sum[j] % k
    const remainder = prefixSum % k

    // 如果余数已经出现过
    if (map.has(remainder)) {
      const prevIndex = map.get(remainder)
      // 题目要求子数组长度至少为 2
      if (i - prevIndex >= 2) {
        return true
      }
    } else {
      // 只有当余数不存在时才存入，因为我们需要保持这个余数对应的下标尽可能小
      // 这样 i - prevIndex 才更容易 >= 2
      map.set(remainder, i)
    }
  }

  return false
}

• 时间复杂度：$O(N)$，其中 N 是数组 nums 的长度
• 空间复杂度：$O(min(N,K))$，哈希表最多存储 $min(N,K)$ 个不同的余数

算法思路：

题目要求判断是否存在一个长度至少为 2 的连续子数组，其元素和为 k 的倍数，我们可以暴力枚举所有可能的子数组来判定，但更好的做法是通过 同余定理 来优化判定流程，这样可以避免枚举所有子数组。

核心公式 => 同余定理：

$$(a-b)\equiv 0(\mathrm{mod}k)⟺a\equiv b(\mathrm{mod}k)$$$$(a-b)\mathrm{\%}k==0⟺a\mathrm{\%}k==b\mathrm{\%}k$$

在本题中，如果前缀和同余：

$$\{\begin{array}{l}a=prefixSum[i]\text{（当前索引的前缀和）}\\ b=prefixSum[j]\text{（之前某个索引的前缀和）}\\ i>j\end{array}$$$$a\mathrm{\%}k==b\mathrm{\%}k\text{（如果两个前缀和同余）}$$$$\Rightarrow (a-b)\mathrm{\%}k==0\text{（意味着子数组 nums[j+1...i] 的和是 k 的倍数）}$$

实现步骤：

• 维护一个哈希表 map，记录 prefixSum % k 的余数及其第一次出现的下标
• 初始化 map.set(0, -1)
  • 将前缀和为 0 的索引设为 -1 的目的是为了处理从下标 0 开始的子数组
  • 即 $sum[0...i]\mathrm{\%}k==0$ 的情况
• 遍历数组，计算当前的前缀和 prefixSum 和余数 remainder
  • 如果 remainder 已经在 map 中存在：
    • 取出之前记录的下标 prevIndex
    • 如果当前下标 i 满足 i - prevIndex >= 2，则说明找到了符合条件的子数组，返回 true
  • 如果 remainder 不在 map 中，将其存入 map.set(remainder, i)
    • 注意：如果已经存在，不要更新下标，因为我们要找的是最长的或者说尽早出现的下标，以满足长度 >= 2 的条件

3. 🔗 引用

• 百度百科 - 同余定理