连续子数组和

字数 2559 2025-12-18 03:43:24

连续子数组和

题目描述
给定一个包含非负数的数组和一个整数目标值 k，请判断该数组中是否存在一个连续的子数组，其长度至少为 2，且该子数组的元素总和为 k 的整数倍。如果存在，返回 true；否则，返回 false。

示例
输入：nums = [23, 2, 4, 6, 7], k = 6
输出：true
解释：子数组 [2, 4] 的长度为 2，总和为 6，是 6 的整数倍。

解题过程循序渐进讲解

步骤 1：理解问题与暴力解法思路

题目要求找到长度至少为 2 的连续子数组，其元素总和是 k 的整数倍。
最直接的思路是：

枚举所有可能的子数组起点 i 和终点 j（j > i，确保长度 ≥ 2）。
计算子数组 nums[i..j] 的和 sum(i, j)。
检查 sum(i, j) % k == 0 是否成立。

时间复杂度：计算每个子数组的和需要 O(n²) 时间，如果直接累加则总体为 O(n³)，用前缀和优化可降至 O(n²)。
但题目通常要求更高效的解法，因此需要进一步优化。

步骤 2：前缀和与同余定理引入

定义前缀和 prefix[i] 表示 nums[0] + nums[1] + ... + nums[i-1]（即前 i 个元素的和）。
特别地，prefix[0] = 0。
则子数组 nums[i..j] 的和 = prefix[j+1] - prefix[i]。

题目要求：(prefix[j+1] - prefix[i]) % k == 0。
根据模运算性质：

(a - b) % k == 0 等价于 a % k == b % k。

因此，问题转化为：
是否存在两个前缀和 prefix[i] 和 prefix[j+1]（其中 j+1 - i >= 2，即子数组长度 ≥ 2），它们对 k 取模的结果相等？

步骤 3：哈希表的作用

我们需要快速查找之前是否出现过相同的前缀和模 k 值，并记录对应的下标（用来判断子数组长度是否 ≥ 2）。
哈希表 map 的键是 prefix_sum % k（即前缀和模 k 的值），值是该模值第一次出现时的前缀下标（即 i）。

遍历数组时：

计算当前前缀和 curr_prefix 并取模 mod = curr_prefix % k。
（注意：由于 k 可能为 0，需要特殊处理，后面会说明。）
检查哈希表中是否存在键 mod：
- 如果存在，且当前下标与哈希表中记录的下标之差 ≥ 2，则找到符合条件的子数组。
- 如果不存在，则将 (mod, 当前下标) 存入哈希表。

但这里有一个关键细节：我们需要判断子数组长度 ≥ 2，所以哈希表应该记录的是前缀和模值第一次出现的位置。
此外，初始时应该将 (0, -1) 存入哈希表，表示前缀和为 0 时下标为 -1（即还没有任何元素时的状态），这样可以处理从数组开头开始的子数组。

步骤 4：处理 k = 0 的情况

如果 k = 0，题目要求子数组总和为 0 的整数倍，即总和为 0。
此时模运算 % 0 没有定义，需要单独处理：
判断是否存在长度 ≥ 2 的子数组其元素总和为 0。
可以用哈希表记录前缀和本身（而不是模值），检查之前是否出现过相同的前缀和且下标差 ≥ 2。

步骤 5：算法步骤总结

如果 k == 0：
- 遍历数组，维护前缀和 curr_sum 和哈希表 seen（键为前缀和，值为该前缀和第一次出现的下标）。
- 如果 curr_sum 已在 seen 中存在，且当前下标与 seen[curr_sum] 的差 ≥ 2，返回 true。
- 否则如果 curr_sum 不在 seen 中，则存入。
- 遍历结束未找到则返回 false。
如果 k != 0：
- 初始化哈希表 seen，键为前缀和模 k 的值，值为该模值第一次出现的下标。
- 初始存入 (0, -1)，表示前缀和为 0 时下标为 -1。
- 遍历数组，计算当前前缀和 curr_sum，计算 mod = curr_sum % k。
- 如果 mod 已在 seen 中，且当前下标与 seen[mod] 的差 ≥ 2，返回 true。
- 否则如果 mod 不在 seen 中，存入 (mod, 当前下标)。
- 遍历结束未找到则返回 false。

步骤 6：示例演算

以 nums = [23, 2, 4, 6, 7], k = 6 为例：

初始化 seen = {0: -1}, curr_sum = 0。

i = 0, num = 23
curr_sum = 23, mod = 23 % 6 = 5
seen 中没有 5，存入 {0: -1, 5: 0}
i = 1, num = 2
curr_sum = 25, mod = 25 % 6 = 1
seen 中没有 1，存入 {0: -1, 5: 0, 1: 1}
i = 2, num = 4
curr_sum = 29, mod = 29 % 6 = 5
seen 中有 5，对应下标 0，当前下标 2，差为 2 (≥ 2)，找到子数组 [2, 4] 总和为 6，返回 true。

步骤 7：边界情况与注意事项

数组长度小于 2 时直接返回 false。
注意负数情况：题目已说明数组元素非负，但 k 可以是任意整数。若数组元素可能为负数，取模时需要注意不同语言对负数取模的结果可能不同，通常统一处理为 (curr_sum % k + k) % k 来保证模值为非负。
时间复杂度 O(n)，空间复杂度 O(min(n, k))（因为模值范围在 0 到 |k|-1 之间）。

总结
本题核心是利用前缀和与同余定理，将子数组和是否为 k 的倍数转化为前缀和模 k 值是否相等的问题，再通过哈希表记录模值首次出现的位置，实现 O(n) 时间复杂度的求解。

连续子数组和题目描述给定一个包含非负数的数组和一个整数目标值 k ，请判断该数组中是否存在一个连续的子数组，其长度至少为 2，且该子数组的元素总和为 k 的整数倍。如果存在，返回 true ；否则，返回 false 。示例输入： nums = [23, 2, 4, 6, 7] , k = 6 输出： true 解释：子数组 [2, 4] 的长度为 2，总和为 6，是 6 的整数倍。解题过程循序渐进讲解步骤 1：理解问题与暴力解法思路题目要求找到长度至少为 2 的连续子数组，其元素总和是 k 的整数倍。最直接的思路是：枚举所有可能的子数组起点 i 和终点 j （ j > i ，确保长度 ≥ 2）。计算子数组 nums[i..j] 的和 sum(i, j) 。检查 sum(i, j) % k == 0 是否成立。时间复杂度：计算每个子数组的和需要 O(n²) 时间，如果直接累加则总体为 O(n³)，用前缀和优化可降至 O(n²)。但题目通常要求更高效的解法，因此需要进一步优化。步骤 2：前缀和与同余定理引入定义前缀和 prefix[i] 表示 nums[0] + nums[1] + ... + nums[i-1] （即前 i 个元素的和）。特别地， prefix[0] = 0 。则子数组 nums[i..j] 的和 = prefix[j+1] - prefix[i] 。题目要求： (prefix[j+1] - prefix[i]) % k == 0 。根据模运算性质： (a - b) % k == 0 等价于 a % k == b % k 。因此，问题转化为：是否存在两个前缀和 prefix[i] 和 prefix[j+1] （其中 j+1 - i >= 2 ，即子数组长度 ≥ 2），它们对 k 取模的结果相等？步骤 3：哈希表的作用我们需要快速查找之前是否出现过相同的前缀和模 k 值，并记录对应的下标（用来判断子数组长度是否 ≥ 2）。哈希表 map 的键是 prefix_sum % k （即前缀和模 k 的值），值是该模值第一次出现时的前缀下标（即 i ）。遍历数组时：计算当前前缀和 curr_prefix 并取模 mod = curr_prefix % k 。（注意：由于 k 可能为 0，需要特殊处理，后面会说明。）检查哈希表中是否存在键 mod ：如果存在，且当前下标与哈希表中记录的下标之差 ≥ 2，则找到符合条件的子数组。如果不存在，则将 (mod, 当前下标) 存入哈希表。但这里有一个关键细节：我们需要判断子数组长度 ≥ 2，所以哈希表应该记录的是前缀和模值第一次出现的位置。此外，初始时应该将 (0, -1) 存入哈希表，表示前缀和为 0 时下标为 -1（即还没有任何元素时的状态），这样可以处理从数组开头开始的子数组。步骤 4：处理 k = 0 的情况如果 k = 0 ，题目要求子数组总和为 0 的整数倍，即总和为 0。此时模运算 % 0 没有定义，需要单独处理：判断是否存在长度 ≥ 2 的子数组其元素总和为 0。可以用哈希表记录前缀和本身（而不是模值），检查之前是否出现过相同的前缀和且下标差 ≥ 2。步骤 5：算法步骤总结如果 k == 0 ：遍历数组，维护前缀和 curr_sum 和哈希表 seen （键为前缀和，值为该前缀和第一次出现的下标）。如果 curr_sum 已在 seen 中存在，且当前下标与 seen[curr_sum] 的差 ≥ 2，返回 true 。否则如果 curr_sum 不在 seen 中，则存入。遍历结束未找到则返回 false 。如果 k != 0 ：初始化哈希表 seen ，键为前缀和模 k 的值，值为该模值第一次出现的下标。初始存入 (0, -1) ，表示前缀和为 0 时下标为 -1。遍历数组，计算当前前缀和 curr_sum ，计算 mod = curr_sum % k 。如果 mod 已在 seen 中，且当前下标与 seen[mod] 的差 ≥ 2，返回 true 。否则如果 mod 不在 seen 中，存入 (mod, 当前下标) 。遍历结束未找到则返回 false 。步骤 6：示例演算以 nums = [23, 2, 4, 6, 7] , k = 6 为例：初始化 seen = {0: -1} , curr_sum = 0 。 i = 0, num = 23 curr_sum = 23 , mod = 23 % 6 = 5 seen 中没有 5，存入 {0: -1, 5: 0} i = 1, num = 2 curr_sum = 25 , mod = 25 % 6 = 1 seen 中没有 1，存入 {0: -1, 5: 0, 1: 1} i = 2, num = 4 curr_sum = 29 , mod = 29 % 6 = 5 seen 中有 5，对应下标 0，当前下标 2，差为 2 (≥ 2)，找到子数组 [ 2, 4] 总和为 6，返回 true 。步骤 7：边界情况与注意事项数组长度小于 2 时直接返回 false 。注意负数情况：题目已说明数组元素非负，但 k 可以是任意整数。若数组元素可能为负数，取模时需要注意不同语言对负数取模的结果可能不同，通常统一处理为 (curr_sum % k + k) % k 来保证模值为非负。时间复杂度 O(n)，空间复杂度 O(min(n, k))（因为模值范围在 0 到 |k|-1 之间）。总结本题核心是利用前缀和与同余定理，将子数组和是否为 k 的倍数转化为前缀和模 k 值是否相等的问题，再通过哈希表记录模值首次出现的位置，实现 O(n) 时间复杂度的求解。