哈希算法题目：连续子数组和 题目描述 给定一个包含非负数的数组和一个整数 k，判断该数组是否存在一个连续子数组，其长度至少为 2，且该子数组的元素之和是 k 的倍数。 示例 1 输入: [ 23, 2, 4, 6, 7 ], k = 6 输出: True 解释: 子数组 [ 2, 4 ] 的长度为 2，其和为 6，是 6 的倍数。 示例 2 输入: [ 23, 2, 6, 4, 7 ], k = 6 输出: True 解释: 子数组 [ 23, 2, 6, 4, 7 ] 本身就是一个连续子数组，其和为 42，是 6 的倍数。 解题思路 暴力解法（不可取） ：枚举所有长度至少为 2 的子数组，计算其和并判断是否为 k 的倍数。时间复杂度为 O(n²)，对于大规模数据会超时。 哈希表优化 ：利用前缀和与同余定理来优化。核心思想是，如果两个前缀和对 k 的余数相同，那么这两个前缀和之间的子数组和就是 k 的倍数。 逐步讲解 步骤 1: 理解前缀和 定义前缀和数组 prefixSum ，其中 prefixSum[i] 表示从第 0 个元素到第 i 个元素的和。 例如，对于数组 [a, b, c] ： prefixSum[0] = a prefixSum[1] = a + b prefixSum[2] = a + b + c 步骤 2: 利用同余定理 同余定理：如果 (prefixSum[j] - prefixSum[i]) % k == 0 ，则 prefixSum[j] % k == prefixSum[i] % k 。 这意味着，如果两个前缀和对 k 的余数相同，那么它们之间的子数组和（即 prefixSum[j] - prefixSum[i] ）是 k 的倍数。 步骤 3: 处理特殊情况 当 k = 0 时，不能做取模运算，需要单独处理。此时问题转化为是否存在长度至少为 2 的子数组，其和为 0。 当子数组长度至少为 2，意味着两个前缀和的下标差至少为 2。 步骤 4: 哈希表存储余数 使用哈希表存储每个余数第一次出现的位置（即前缀和的下标）。 遍历数组，计算当前前缀和除以 k 的余数。 如果该余数已经在哈希表中存在，且当前下标与哈希表中存储的下标之差至少为 2，则找到满足条件的子数组。 如果该余数不在哈希表中，则将其当前下标存入哈希表。 步骤 5: 示例演示 以示例 1 为例，数组为 [23, 2, 4, 6, 7] ，k = 6： 初始化：哈希表 map ，预存入 {0: -1} 处理从开头开始的子数组。 i = 0: 前缀和 = 23，余数 = 23 % 6 = 5，map 中无 5，存入 {0: -1, 5: 0} i = 1: 前缀和 = 25，余数 = 25 % 6 = 1，map 中无 1，存入 {0: -1, 5: 0, 1: 1} i = 2: 前缀和 = 29，余数 = 29 % 6 = 5，map 中有 5（下标 0），当前下标 2 - 0 = 2 ≥ 2，找到子数组 [ 2, 4 ]，返回 True。 复杂度分析 时间复杂度：O(n)，只需遍历一次数组。 空间复杂度：O(min(n, k))，哈希表最多存储 k 个余数。 通过这种思路，可以高效解决连续子数组和的问题。