LeetCode 523. 连续的子数组和
目录
题目描述
题意分析
给一个非负整数数组和一个整数 k，问数组里是否存在一个「好子数组」：它必须是连续的、长度至少为 2，并且元素之和是 k 的倍数。只要存在就返回
true，否则返回false。第一个必须抠住的约束是「长度至少为 2」。这条限制看起来不起眼，却是本题几乎所有错误答案的来源：只要漏掉它，任何一个本身就是 k 的倍数的单个元素都会被误判成答案，而题目明确不认单元素子数组。
第二个是「k 的倍数」这个措辞：0 也是 k 的倍数（$0 = 0 \times k$），所以和为 0 的子数组同样合法，
[0, 0]这样的输入对任何 k 都应该返回true。这一点和「和恰好等于 k」的题目有本质区别。第三个是 k 本身可能为 0（历史版本的用例里出现过）。一旦 k 为 0，「是 k 的倍数」就退化成「和恰好为 0」，任何取模运算在这里都是非法操作，必须单独处理。
边界上还要注意：数组长度可能只有 1，此时凑不出长度为 2 的子数组，直接返回
false；元素全为非负也意味着前缀和单调不减，但这并不能省掉哈希表，因为「和是 k 的倍数」不是单调性质，双指针滑窗对它不成立。
解法：前缀和取模 + 最早位置
核心思路
设前缀和
\[prefix[r] \bmod \lvert k\rvert = prefix[l] \bmod \lvert k\rvert\]prefix[i]表示前i个元素之和，则子数组[l, r)的和为prefix[r] - prefix[l]。当k != 0时，这段和是k的倍数，当且仅当两个前缀和对\lvert k\rvert的余数相同：因此遍历前缀和时，用哈希表记录「每个余数最早出现的前缀下标」。再次遇到同一余数时，两下标之差就是子数组长度；只要差至少为 2，就找到答案。只保留最早位置很重要：它能得到最长候选区间，覆盖更晚的位置只会让后续区间变短。
初始化
0 -> 0，表示空前缀的和为 0、前缀下标为 0，这样从数组开头出发的区间也无需特判。循环不变量是：处理prefix[i]前，表中保存了此前每种余数的最早下标；因此一次查询即可判断是否存在以i - 1结尾的合法子数组。
k = 0时不能取模。此时「和是 0 的倍数」等价于区间和为 0，所以把原始前缀和作为键，仍可复用同一套逻辑。k < 0与\lvert k\rvert的整除关系相同；代码还会把负余数归一化，因而即使数组元素扩展为负数也成立。
解题步骤
- 令
first[0] = 0，前缀和sum = 0；将模数统一为|k|。- 依次计算
prefix[1]到prefix[n]，每次得到当前键：k != 0时取规范化余数，k = 0时直接用前缀和。- 若键已出现，检查
i - first[key] >= 2，成立立即返回true；长度不足时不要覆盖最早位置。- 若键首次出现，记录
first[key] = i。- 遍历结束仍未命中，返回
false。以
nums = [23,2,4,6,7]、k = 6为例，前缀和 23 与 29 的余数都是 5，对应前缀下标 1 和 3，长度为 2，所以子数组[2,4]合法。反例nums = [3,1]、k = 3中，前缀下标 1 与空前缀余数相同，但长度只有 1，不能返回true。
代码实现
import java.util.HashMap;
import java.util.Map;
class Solution {
public boolean checkSubarraySum(int[] nums, int k) {
Map<Long, Integer> first = new HashMap<>();
first.put(0L, 0);
long sum = 0;
long mod = Math.abs((long) k);
for (int i = 1; i <= nums.length; i++) {
sum += nums[i - 1];
long key = mod == 0 ? sum : (sum % mod + mod) % mod;
Integer start = first.get(key);
if (start != null) {
if (i - start >= 2) {
return true;
}
} else {
first.put(key, i);
}
}
return false;
}
}
func checkSubarraySum(nums []int, k int) bool {
first := map[int64]int{0: 0}
var sum int64
mod := int64(k)
if mod < 0 {
mod = -mod
}
for i, num := range nums {
sum += int64(num)
key := sum
if mod != 0 {
key = (sum%mod + mod) % mod
}
if start, exists := first[key]; exists {
if i+1-start >= 2 {
return true
}
} else {
first[key] = i + 1
}
}
return false
}
复杂度分析
- 时间复杂度：$O(n)$，只遍历一次数组，哈希表操作均摊为 $O(1)$。
- 空间复杂度：
k != 0时为 $O(\min(n, \lvert k\rvert))$，k = 0时最坏为 $O(n)$。
关键点总结
- 区间和问题先写成两个前缀和之差，再用同余关系消掉区间枚举。
- 哈希表必须保留每个键的最早位置，才能最大化长度；命中但长度不足时也不能更新。
0 -> 0代表空前缀，使从下标 0 开始的区间自然进入统一逻辑。k = 0时比较原始前缀和；k < 0时使用|k|；存在负数时还要规范化余数。- 使用 64 位前缀和与模数，既避免累加溢出，也能安全处理 Java 的
Integer.MIN_VALUE。
易错点总结
- 命中相同余数就直接返回，会把
nums = [3,1]、k = 3的单元素前缀误判为合法；必须检查长度至少为 2。- 覆盖最早位置会缩短后续候选区间，可能漏解；键已存在时只检查，不更新。
- 忘记预置空前缀会漏掉从数组开头开始的答案，例如
[1,2]、k = 3。k = 0时执行取模会除零；应改为判断两个前缀和是否相等。- 直接对负
k取模或写Math.abs(k)都不够稳妥：不同语言的负余数规则不同，且 Java 的Math.abs(Integer.MIN_VALUE)仍为负数；先转 64 位再取绝对值。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 525. 连续数组 | 中等 | 0/1 转 ±1 后求最长等和区间 |
| 560. 和为 K 的子数组 | 中等 | 前缀和之差恰好为 K 的计数 |
| 930. 和相同的二元子数组 | 中等 | 二元数组定和子数组计数 |
| 974. 和可被 K 整除的子数组 | 中等 | 同余分组求方案数而非存在性 |
| 1010. 总持续时间可被 60 整除的歌曲 | 中等 | 余数互补配对 |
| 1590. 使数组和能被 P 整除 | 中等 | 删除最短子数组凑余数 |